אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הנדב הנכון (שיחה | תרומות) מאין תקציר עריכה |
|||
שורה 29:
אלגוריתם רו של פולרד מנסה לייצר "סדרה פסידו-אקראית" של אלמנטים מהחבורה בהתבסס על [[אלגוריתם מונטה קרלו|רעיון מונטה קרלו]] וחיפוש אחר התנגשויות, כלומר שני אלמנטים זהים בסדרה. אם נמצאה התנגשות הדבר מוביל לפתרון בעיית הלוגריתם הבדיד בהסתברות גבוהה. שני רעיונות מרכזיים של פולרד הם '''פונקציה איטרטיבית''' אקראית קלה לחישוב, איתה מכינים את הסדרה הפסאודו-אקראית ואלגוריתם '''מציאת מחזוריות''' שמנסה למצוא בה התנגשות בזמן הקצר ביותר ללא שימוש בטבלאות. לצורך הפשטות נניח שנתונה חבורה ציקלית <math>G</math> מסדר <math>n</math> ראשוני.
תחילה מחלקים את <math>G</math> לשלוש קבוצות בגודל זהה בקירוב <math>S_1,S_2,S_3</math>, בחלוקה לוגית בהתבסס על כלל מנחה קל לבדיקה. אפשר למשל לחלק לפי משקלו של כל אלמנט באופן הבא הקבוצה <math>S_1</math> תכיל את כל האלמנטים: <math>\textstyle 0<x_i<\frac{1}{3}n</math>, הקבוצה <math>S_2</math> את האלמנטים <math>\textstyle\frac{1}{3}n<x_i<\frac{2}{3}n</math> והשלישית <math>\textstyle\frac{2}{3}n<x_i<n</math>. דרך אחרת יותר יעילה היא לחלק לפי הערך של <math>t</math> הסיביות הכי פחות משמעותיות של כל <math>x_i</math> כאשר <math>t</math> תלוי במספר החלוקות (במקרה זה מספיק לבחון את שלוש הסיביות האחרונות). מספר החלוקות
מחשבים [[סדרה]] פסידו-אקראית של אלמנטים מהחבורה לפי הכלל הבא. בוחרים אלמנט התחלתי <math>x_0=1</math> ועבור כל <math>i\ge 0</math> מחשבים:
| |||