בהנחה ש-formula_95, שבכל מקרה עלול לקרות בהסתברות מאוד זניחה. מתוך המשוואה האחרונה אפשר לחלץ את formula_96 על ידי הכפלה בהופכי הכפלי של formula_97.
פירוט מהלכי האלגוריתם.
אלגוריתם רו של פולרד
קלט: החבורה formula_57 מסדר formula_2, יוצר formula_8 והאלמנט formula_39.
פלט: הלוגריתם הבדיד formula_102.
במקרה הנדיר שהאלגוריתם מסתיים בכישלון מגרילים formula_112 אחרים ומתחילים מההתחלה כאשר formula_113.
דוגמה במספרים קטנים.
נתונה תת-חבורה formula_57 של החבורה formula_115 מסדר formula_116 עם היוצר formula_117 ונתון formula_118.
חלוקת האלמנטים של formula_57 לשלוש קבוצות מתבצעת לפי הכלל הבא: מחשבים את formula_120, אם השארית 1 הוא שייך ל-formula_61, אם השארית היא 0 הוא שייך ל-formula_63 ואילו אם השארית היא 2 הוא שייך ל-formula_123. הטבלה הבאה מסכמת את מהלכי האלגוריתם והערכים של formula_87 וכן formula_125 לאחר כל איטרציה. באיטרציה ה-14 נמצאה התנגשות כי formula_126. לכן מחשבים את formula_127 וההופכי שלו formula_128 ולכן formula_129 והפתרון הוא formula_130 מודולו 191.
אלגוריתם רו של פולרד בעקום אליפטי.
עקום אליפטי הוא כלי מתמטי פופולרי המצוי בשימוש נרחב בהצפנה מודרנית בשל העובדה שהוא מאפשר פרמטרים קטנים יותר בפקטור של עשר בקירוב לעומת אלגוריתם כמו RSA. עם עקום אליפטי אפשר ליישם פונקציה חד-כיוונית ואיתה לממש הצפנה אסימטרית המבוססת על בעיה מתמטית כמו בעיית הלוגריתם הבדיד בעקום אליפטי. בעיית הלוגריתם הבדיד בעקום אליפטי מקבילה לבעיה הכללית והיא כדלהלן:
השלם formula_131 נקרא הלוגריתם הבדיד של הנקודה formula_132 בבסיס הנקודה formula_133 או בקיצור formula_134. אם הפרמטרים של העקום formula_135 נבחרו בזהירות כדי להבטיח שלא יהיו קיצורי דרך לפתרון הבעיה בעקום זה, הדרך הטובה ביותר לפתרונה היא באמצעות אלגוריתם רו של פולרד בסיבוכיות של formula_136. הסימון formula_137 מייצג את כל הנקודות שהן כפולות של formula_133. (כגון formula_139 וכן הלאה עד formula_2). במילים אחרות, הנקודה formula_132 היא תוצאה של חיבור הנקודה formula_133 בעצמה (הנקראת בקיצור POINT_DBL) בדיוק formula_131 פעמים והבעיה היא לגלות כמה פעמים בוצע החיבור, קרי לגלות את ערכו של formula_131. לא קיימת דרך פשוטה לבצע זאת כי המסלול של הנקודות נראה אקראי. שיטת כוח גס אינה מעשית משום שבמקרה הממוצע יש צורך לבדוק לפחות מחצית מהנקודות עד שנמצא formula_145. אם formula_42 כוח גס אינו מעשי. כמובן שיש לשים לב של-formula_2 יש לפחות גורם ראשוני אחד גדול דיו. שאם לא כן אפשר לנצל את אלגוריתם פוליג-הלמן בזמן שהוא ביחס ישיר לגודל הגורמים הראשוניים שלו. למעשה ככל שהגורם הראשוני שלו (לפחות אחד מהם) גדול יותר סיבוכיות ההתקפה תהיה גבוהה יותר.
תיאור כללי.
כמו בחבורה ציקלית, הרעיון של אלגוריתם רו בעקום אליפטי הוא למצוא שני זוגות שלמים (formula_148) וכן (formula_149) מודולו formula_2 המקיימים:
ואז
ולכן
מזה נובע שאפשר לחשב את formula_134 על ידי formula_155.
הדרך הישירה למצוא זוגות המקיימים את המשוואה האמורה היא על ידי בחירה אקראית ואחסון בטבלה. אם מכינים טבלה המכילה את כל השלשות: (formula_156) וממיינים לפי הערך השלישי, מובטח שבסופו של דבר הערך הזה יופיע פעם נוספת מה שיאפשר לגלות את הלוגריתם הבדיד כאמור. תופעה שבה הערך השלישי מופיע פעמיים כאשר הערכים האחרים שונים נקראת "התנגשות". לפי פרדוקס יום ההולדת מספר הניסיונות הצפוי לפני שתופיע התנגשות הוא בערך formula_157 שזה בערך formula_158. אולם החסרון בשיטה זו הוא שיש צורך בזיכרון רב, ליתר דיוק formula_157 שלשות. אלגוריתם רו מנסה להימנע משימוש בזיכרון על ידי שיטת הצב והארנב. מגדירים פונקציה איטרטיבית אקראית formula_160 כך שבהינתן formula_161 והערכים formula_162 ו-formula_163 כך שמתקיים formula_164 יהיה קל לחשב את formula_165 ואת formula_166 כך שמתקיים formula_167.
לדוגמה, אם מחלקים את החבורה הציקלית formula_137 ל-formula_169 רשימות בגודל זהה בקירוב (למשל formula_170), מציבים כל נקודה formula_171 ברשימה המתאימה formula_172 אם הערך של 5 הסיביות הכי פחות משעותיות של הקואורדינטה formula_28 של הנקודה formula_171 הוא formula_175. נניח ששיטת חלוקה זו תסומן ב-formula_176 ונניח שהערכים formula_177 ו-formula_178 הם שלמים אקראיים כלשהם הנמוכים מ-formula_2 כאשר formula_180 מתפרס על פני כל הרשימות של formula_169, במקרה זה פונקציה אקראית איטרטיבית יכולה להיות:
ולכן אם formula_164 אז הפונקציה האקראית היא formula_185 כאשר formula_186 וכן formula_187.
כל נקודה התחלתית formula_188 מגדירה סדרה אחרת formula_189 של נקודות כאשר כל נקודה מחושבת על ידי הנקודה הקודמת, formula_190. היות שהחבורה הזו סופית בהכרח שתיגרם התנגשות, כלומר ערך של formula_171 כלשהו יופיע שוב ומנקודה זו ואילך הסדרה תחזור על עצמה במעגל אין סופי. כלומר יופיע האינדקס הקטן ביותר formula_66 המקיים formula_193עבור formula_194 כלשהו ומכאן ואילך formula_195 עבור כל formula_196. כאן formula_66 הוא אורך השובל ו-formula_194 הוא היקף מעגל במונחים של מספר האיטרציות של הפונקציה האיטרטיבית האקראית. אם formula_199 היא פונקציה אקראית אז ההתנגשות הראשונה צפויה לקרות לאחר formula_157 צעדים בקירוב. אורך השובל הוא formula_201 ואורך המעגל צריך להיות formula_202 בקירוב.
התנגשות היא מצב שבו formula_203 כאשר formula_85 ואותה אפשר למצוא ללא צורך בזיכרון באמצעות שיטת פלויד או שיטת הצב והארנב. בשיטה זו מחשבים בכל צעד את הנקודות formula_171 ו-formula_206 ומנסים למצוא התאמה. מספר הזוגות הצפוי שיש לבדוק הוא לכל הפחות formula_66 זוגות ולכל היותר formula_208 זוגות, עד שתמצא התנגשות. ליתר דיוק בהנחה ש-formula_199 אקראית מספר הזוגות הצפוי שצריך לבדוק עד שתמצא התנגשות הוא formula_210. מספר החישובים שיש לבצע בעקום האליפטי הוא בערך formula_211 פעולות חיבור נקודות.
פירוט מהלכי האלגוריתם.
אלגוריתם רו של פולרד לחישוב לוגריתם בדיד בעקום אליפטי.
קלט: הנקודה formula_212 מסדר formula_2 והנקודה formula_214
פלט: הלוגריתם הבדיד formula_134.
דוגמה במספרים קטנים.
נתון העקום formula_235 עם המשוואה formula_236. נקודה formula_237 היא מסדר ראשוני formula_238. תהי הנקודה formula_239. כדי למצוא את formula_134 מגדירים תחילה formula_241 ובוחרים פונקציית חלוקה formula_242 לפי הכלל:
בוחרים ומחשבים ארבע שלשות:
הטבלה הבאה מציגה את השלשות (formula_248) ו-(formula_249) המתקבלות לאחר הצעד הרביעי באלגוריתם עבור המקרה formula_250.
אפשר לראות בשורה האחרונה בטבלה שהאלגוריתם מצא התנגשות כי:
לכן
שיפורים.
בגלל הפופולריות של עקומים אליפטיים בקריפטוגרפיה, נעשה מאמץ לשפר את אלגוריתם רו של פולרד בין היתר על ידי עיבוד מקבילי. נניח שזמינים formula_253 מחשבים לצורך פתרון הבעיה. הדרך הנאיבית היא להריץ את האלגוריתם על כל מחשב בנפרד עם נקודות התחלה אקראיות שונות, עד שאחד מהם יגלה התנגשות. שיטה זו אינה מנצלת את פוטנציאל המקביליות כי השיפור בביצועים הוא בפקטור formula_254 לכל היותר. פול ואן-אורשוט ומייקל ויינר הציעו גרסה מקבילית של אלגוריתם רו שמניבה שיפור בביצועים בפקטור של formula_253. הרעיון הוא לאפשר לכל הסדרות formula_189 של כל המעבדים להתנגש אחת עם השנייה. ביתר פירוט, כל מעבד בוחר לעצמו נקודת התחלה formula_257 באופן אקראי בנפרד מהאחרים, אולם כל המעבדים משתמשים באותה פונקציה איטרטיבית כדי לחשב את האלמנט הבא בסדרה formula_258. לכן, אם נוצרת התנגשות בין שתי סדרות, כל הנקודות של שתי הסדרות החל בנקודה שבה הופיעה התנגשות תהיינה זהות. כדי להתאים את אלגוריתם פלויד למציאת מחזוריות בין סדרות נפרדות שנוצרות על ידי מעבדים שונים, נוקטים באסטרטגיה הבאה, בוחרים מאפיין ייחודי קל לזיהוי המשמש כ"נקודה מובחנת" (Distinguished Point). נקודה מובחנת יכולה להיות כזו המכילה למשל רצף של formula_66 אפסים מובילים בקואורדינטה formula_28 שלה. בכל פעם שמעבד נתקל בנקודה מובחנת כזו הוא משדר את הנקודה לשרת מרכזי שאוסף את כל הנקודות המובחנות מכל המעבדים וממיין אותם בזיכרון. אם השרת מקבל בשלב כלשהו נקודה מובחנת שכבר התקבלה קודם לכן, הוא מחשב את הלוגריתם הבדיד ומסיים בהצלחה.
אם הפרופורציה של הנקודות המובחנות ב-formula_137 היא formula_262 הסיכויים לקבל התנגשות הם בערך formula_263 לכן מספר פעולות כפל נקודות בעקום הצפוי מכל מעבד עד שמתקבלת התנגשות אחת הוא
בכך מושגת האצה ליניארית במהירות הביצוע של האלגוריתם ביחס למספר המעבדים הזמינים. ההתקשרות עם השרת המרכזי היא מינימלית וכן אין צורך בתקשורת כלשהי של המחשבים בינם לבין עצמם מלבד עם השרת. אפשר לשלוט בכמות הזיכרון הנדרשת בשרת המרכזי על ידי בחירה נכונה של תכונת ההבחנה באופן כזה שמצד אחד לא תהיה נדירה ויהיה קשה למצוא נקודה כזו אך מצד שני שלא תהיה תדירה מדי ואז כמות הזיכרון עלולה להיות מופרזת.