אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות

בגלל הפופולריות של עקומים אליפטיים בקריפטוגרפיה, נעשה מאמץ לשפר את אלגוריתם רו של פולרד בין היתר על ידי [[עיבוד מקבילי]]. נניח שזמינים <math>M</math> מחשבים לצורך פתרון הבעיה. הדרך הנאיבית היא להריץ את האלגוריתם על כל מחשב בנפרד עם נקודות התחלה אקראיות שונות, עד שאחד מהם יגלה התנגשות. שיטה זו אינה מנצלת את פוטנציאל המקביליות כי השיפור בביצועים הוא בפקטור <math>\sqrt{M}</math> לכל היותר. פול ואן-אורשוט ומייקל ויינר הציעו גרסה מקבילית של אלגוריתם רו שמניבה שיפור בביצועים בפקטור של <math>M</math>{{הערה|Paul C. van Oorschot, Michael J. Wiener, [http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf "Parallel Collision Search with Cryptanalytic Applications"] Journal of Cryptology January 1999, Volume 12, Issue 1, pp 1–28}}. הרעיון הוא לאפשר לכל הסדרות <math>\{X_i\}_{i\ge 0}</math> של כל המעבדים להתנגש אחת עם השניה. ביתר פירוט, כל מעבד בוחר לעצמו נקודת התחלה <math>X_0</math> באופן אקראי בנפרד מהאחרים, אולם כל המעבדים משתמשים באותה פונקציה איטרטיבית כדי לחשב את האלמנט הבא בסדרה <math>X_iX_{i+1}</math>. לכן, אם נוצרת התנגשות בין שתי סדרות, כל הנקודות של שתי הסדרות החל בנקודה שבה הופיעה התנגשות תהיינה זהות. כדי להתאים את אלגוריתם פלויד למציאת מחזוריות בין סדרות נפרדות שנוצרות על ידי מעבדים שונים, נוקטים באסטרטגיה הבאה, בוחרים מאפיין ייחודי קל לזיהוי המשמש כ"נקודת הבחנה" (Distinguished Point). נקודה מובחנת יכולה להיות כזו המכילה למשל רצף של <math>t</math> אפסים מובילים בקואורדינטה <math>x</math> שלה. בכל פעם שמעבד נתקל בנקודה מובחנת כזו הוא משדר את הנקודה לשרת מרכזי שאוסף את כל הנקודות המובחנות מכל המעבדים וממיין אותם בזיכרון. אם השרת מקבל בשלב כלשהו נקודה מובחנת שכבר התקבלה קודם לכן, הוא מחשב את הלוגריתם הדיסקרטי ומסיים בהצלחה.