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

אלגוריתם רו של פולרד מנסה לייצר "סדרה פסידו-אקראית" של אלמנטים מהחבורה בהתבסס על [[אלגוריתם מונטה קרלו|רעיון מונטה קרלו]] וחיפוש אחר התנגשויות, כלומר שני אלמנטים זהים בסדרה. אם נמצאה התנגשות הדבר מוביל לפתרון בעיית הלוגריתם הדיסקרטי בהסתברות גבוהה. שני רעיונות מרכזיים של פולרד הם '''פונקציה איטרטיבית''' אקראית קלה לחישוב, איתה מכינים את הסדרה הפסאודו-אקראית ואלגוריתם '''מציאת מחזוריות''' שמנסה למצוא בה התנגשות בזמן הקצר ביותר ללא שימוש בטבלאות. לצורך הפשטות נניח שנתונה חבורה ציקלית <math>G</math> מסדר <math>n</math> ראשוני. תחילה מחלקים את <math>G</math> לשלוש קבוצות בגודל זהה בקירוב <math>S_1,S_2,S_3</math>, בהתבסס על כלל מנחה פשוט וקל לבדיקה (אפשר למשל לחלק לפי משקלו של כל אלמנט או לפי משקל <math>t</math> הסיביות הכי פחות משמעותיות שלו כאשר <math>t</math> תלוי במספר החלוקות, במקרה זה מספיק לבחון את שלושת הסיביות האחרונות אולם. מספר החלוקות הינו שרירותי וניתן לשינוי, אך יש צורך לשים לב לכמה היבטים חשובים בנוגע לחלוקה למשל <math>1\notin S_2</math>). ביתר פירוט, מגדירים [[סדרה]] של אלמנטים מהחבורה לפי הכלל הבא. בוחרים אלמנט התחלתי <math>x_0=1</math> ומחשבים את האלמנטים הבאים אחריו לפי: