אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 68:
===דוגמה במספרים קטנים===
נתונה תת חבורה <math>G</math> של החבורה <math>\mathbb{Z}_{383}^*</math> מסדר <math>n=191</math> עם היוצר <math>\alpha=2</math> ונתון <math>\beta=228</math>.
חלוקת האלמנטים של <math>G</math> לשלוש קבוצות מתבצעת לפי הכלל הבא: מחשבים את <math>x\text{ mod }3</math>, אם השארית 1 הוא שייך ל-<math>S_1</math>, אם השארית היא 0 הוא שייך ל-<math>S_2</math> ואילו אם השארית היא 2 הוא שייך ל-<math>S_3</math>. הטבלה הבאה מסכמת את מהלכי האלגוריתם והערכים של <math>x_i,a_i,b_i</math> וכן <math>x_{2i},a_{2i},b_{2i}</math> לאחר כל איטרציה. באיטרציה ה-14 נמצאה התנגשות כי <math>x_{14}=x_{28}=144</math>. לכן מחשבים את <math>r=38-104=125\text{ (mod }191)</math> וההופכי שלו <math>125^{-1}\equiv 136\text{ (mod }191)</math> ולכן <math>136\cdot(10-12)\equiv 110\text{ (mod }191)</math> והפתרון הוא <math>\log_2 228=110</math> מודולו 191.
<center>
| |||