אלגוריתם רו של פולרד ללוגריתם הבדיד
אלגוריתם רו של פולרד בעקום אליפטי > שיפורים

בגלל הפופולריות של עקומים אליפטיים בקריפטוגרפיה, נעשה מאמץ לשפר את אלגוריתם רו של פולרד בין היתר על ידי עיבוד מקבילי. נניח שזמינים  M מחשבים לצורך פתרון הבעיה. הדרך הנאיבית היא להריץ את האלגוריתם על כל מחשב בנפרד עם נקודות התחלה אקראיות שונות, עד שאחד מהם יגלה התנגשות. שיטה זו אינה מנצלת את פוטנציאל המקביליות כי השיפור בביצועים הוא בפקטור  {\sqrt {M}} לכל היותר. פול ואן-אורשוט ומייקל ויינר הציעו גרסה מקבילית של אלגוריתם רו שמניבה שיפור בביצועים בפקטור של  M. הרעיון הוא לאפשר לכל הסדרות  \{X_{i}\}_{i\geq 0} של כל המעבדים להתנגש אחת עם השנייה. ביתר פירוט, כל מעבד בוחר לעצמו נקודת התחלה  X_{0} באופן אקראי בנפרד מהאחרים, אולם כל המעבדים משתמשים באותה פונקציה איטרטיבית כדי לחשב את האלמנט הבא בסדרה  X_{i+1}. לכן, אם נוצרת התנגשות בין שתי סדרות, כל הנקודות של שתי הסדרות החל בנקודה שבה הופיעה התנגשות תהיינה זהות. כדי להתאים את אלגוריתם פלויד למציאת מחזוריות בין סדרות נפרדות שנוצרות על ידי מעבדים שונים, נוקטים באסטרטגיה הבאה, בוחרים מאפיין ייחודי קל לזיהוי המשמש כ"נקודה מובחנת" (Distinguished Point). נקודה מובחנת יכולה להיות כזו המכילה למשל רצף של  t אפסים מובילים בקואורדינטה  x שלה. בכל פעם שמעבד נתקל בנקודה מובחנת כזו הוא משדר את הנקודה לשרת מרכזי שאוסף את כל הנקודות המובחנות מכל המעבדים וממיין אותם בזיכרון. אם השרת מקבל בשלב כלשהו נקודה מובחנת שכבר התקבלה קודם לכן, הוא מחשב את הלוגריתם הבדיד ומסיים בהצלחה.
אם הפרופורציה של הנקודות המובחנות ב- \langle P\rangle  היא  \theta  הסיכויים לקבל התנגשות הם בערך  1/\theta  לכן מספר פעולות כפל נקודות בעקום הצפוי מכל מעבד עד שמתקבלת התנגשות אחת הוא
בכך מושגת האצה ליניארית במהירות הביצוע של האלגוריתם ביחס למספר המעבדים הזמינים. ההתקשרות עם השרת המרכזי היא מינימלית וכן אין צורך בתקשורת כלשהי של המחשבים בינם לבין עצמם מלבד עם השרת. אפשר לשלוט בכמות הזיכרון הנדרשת בשרת המרכזי על ידי בחירה נכונה של תכונת ההבחנה באופן כזה שמצד אחד לא תהיה נדירה ויהיה קשה למצוא נקודה כזו אך מצד שני שלא תהיה תדירה מדי ואז כמות הזיכרון עלולה להיות מופרזת.
דרך נוספת לשפר ביצועים היא על ידי שימוש באוטומורפיזם. יהי  \psi :\langle P\rangle \rightarrow \langle P\rangle  אוטומורפיזם של חבורה, כאשר  P היא נקודה בעקום מסדר  n. בהנחה שקל לחשב את  \psi  והיא מסדר  t. כלומר  t הוא השלם הקטן ביותר כך ש- \psi ^{t}(R)=R עבור כל  R ב- \langle P\rangle . מגדירים יחס שקילות על  \langle P\rangle  המסומן  \sim  על ידי
כאשר  l הוא המחלק הקטן ביותר של  t המקיים  \psi ^{l}(R)=R.
הרעיון בהאצת האלגוריתם הוא לשנות את פונקציית האיטרציה  f שתהיה מעל מחלקת השקילות  [R]. כדי לעשות זאת מגדירים הצגה קנונית של  {\overline {R}} של כל מחלקת שקילות  [R]. למשל  {\overline {R}} יכולה להיות הנקודה ב- [R] שהקואורדינטה  x שלה היא השלם הקטן ביותר. או למשל העתקת השלילה  \psi (P)=-P. שאז אפשר להגדיר את פונקציית האיטרציה  g על ידי
אם נניח שקיים שלם  \lambda  המקיים  \psi (P)=\lambda P אז, היות ש- \psi  היא אוטומורפית מתקבל  \psi (R)=\lambda R עבור כל  R\in \langle P\rangle . אם מוצאים שני שלמים  a,b המקיימים  X=aP+bQ אז אפשר לחשב בקלות את השלמים  a',b' המקיימים  {\overline {X}}=a'P+b'Q. אם  {\overline {X}}=\psi ^{j}(X) אז  a'=\lambda ^{j}a{\text{ mod }}n וכן  b'=\lambda ^{j}b{\text{ mod }}n. הפונקציה  g כאן משמשת כפונקציה איטרטיבית באלגוריתם רו בגרסה המקבילית שלו עם  M מעבדים. הנקודה התחלתית של כל סדרה היא  X_{0}'={\overline {X_{0}}} כאשר  X_{0}=a_{0}P+b_{0}Q ו- a_{0},b_{0} הם שלמים אקראיים הנמוכים מ- n. הנקודות הבאות בכל סדרה מחושבות על ידי  X_{i}'=g(X_{i-1}'). אם רוב מחלקות השקילות של  \langle P\rangle  הן באורך  t אז טווח החיפוש מצטמצם ל- n/t ולכן זמן הרצוי המשוער של האלגוריתם בגרסה משופרת זו הוא
זהו שיפור בפקטור של  {\sqrt {t}} במהירות הביצוע. אם משתמשים בהעתקת השלילה  \psi (P)=-P כאוטומורפיזם, מושג שיפור בפקטור של  {\sqrt {2}}.
במקרה של עקום קובליץ  E_{a} מעל  \mathbb {F} _{2} שהוא עקום פופולרי בתקנים של NIST וסרטיקום, העתקת פרובניוס  \tau :E_{a}(\mathbb {F} _{2^{m}})\rightarrow E_{a}(\mathbb {F} _{2^{m}}) המוגדרת על ידי  \tau ({\mathcal {O}})={\mathcal {O}} וכן  \tau (x,y)=(x^{2},y^{2}) גם היא אוטומורפיזם של חבורה מסדר  m והיא קלה לחישוב היות שהעלאה בריבוע היא פעולה קלה בשדה הבינארי (בהצגה פולינומית העלאה בריבוע מודולו 2 שקולה למעשה להכנסת אפסים בין כל הספרות לסירוגין). אם  P\in E_{a} הוא מסדר ראשוני  n כך ש- n^{2} אינו מחלק של סדר העקום המסומן ב- \#E_{a} אז  \tau (P)\in \langle P\rangle  ולכן  \tau  היא אוטומורפית. יהי  \mu =(-1)^{1-a} אפשר להוכיח שאחד מהפתרונות  \lambda  של המשוואה המודולרית  \lambda ^{2}-\mu \lambda +2\equiv 0{\text{ (mod }}n) מקיים  \tau (P)=\lambda P. לכן באופן דומה, הגרסה המקבילית של אלגוריתם רו עם  M מעבדים המשתמשת במחלקות השקילות תחת העתקת פרובניוסמגיעה לזמן ריצה של
ואם מנצלים גם את העתקת השלילה מושג שיפור כולל בזמן הריצה בפקטור של  {\sqrt {2m}}.
למשל ההערכה המקורית שניתנה ב-1996 הייתה שכדי לפתור את בעיית הלוגריתם הבדיד בעקום אליפטי מסדר 113 בהנחה שזמינים 10,000 מעבדים לצורך המשימה כשכל אחד מהם מסוגל לבצע איטרציה אחת בעשר מילישניות, אם  \theta =2^{-30} אז מספר החזרות הצפוי בכל מעבד לפני שמוצאים לוגריתם הוא
שזה שקול בערך ל-1045 ימים או שלוש שנות עיבוד עם כמות של כארבע גיגה-בית זיכרון. הערכות יותר מעודכנות קצת יותר אופטימיות. לדוגמה ב-2002 הצליח צוות חוקרים בראשות קריס מוניקו לפצח את העקום האליפטי ECCp-109 עם 10,000 מחשבים שעבדו במקביל בסך הכול 549 ימים. הם השתמשו בגרסה משופרת של אלגוריתם רו של פולרד והצליחו לפתור את בעיית דיפי-הלמן בעקום זה.