אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 22:
לדוגמה אם נתון המספר הראשוני <math>p=97</math> החבורה <math>\mathbb{Z}_{97}^*</math> היא חבורה ציקלית מסדר <math>n=96</math>. יוצר אפשרי אחד של חבורה זו יכול להיות <math>\alpha=5</math>. (קל לראות שאם מעלים את 5 בחזקת כל המספרים מ-1 עד 96 (מודולו 97) מתקבלים כל האלמנטים של החבורה בלי יוצא מן הכלל לא בהכרח לפי סדר עולה). אם נבחר <math>x=32</math> בחשבון פשוט מתקבל <math>5^{32}\equiv 35\text{ (mod }97)</math> לכן <math>\log_5 35=32</math> בחבורה <math>\mathbb{Z}_{97}^*</math>. וכן, אם <math>y=17</math> אז <math>5^{17}\equiv 83\text{ (mod }97)</math>. אם נתונים האלמנטים <math>5^{32}\equiv 35</math> ו-<math>5^{17}\equiv 83</math> (מודולו 97) בעיית דיפי-הלמן היא לגלות את <math>5^{32\cdot 17}\equiv 61\text{ (mod }97)</math>.
הבעיה נקראת לוגריתם '''בדידי''' בגלל שהיא עוסקת
הדרך הישירה והפשוטה ביותר לפתרון בעיית הלוגריתם הדיסקרטי היא שיטת [[כוח גס]], סריקת כל החזקות של <math>\alpha</math> בזה אחר זה מ-1 עד <math>n</math> עד שמתקבל <math>\beta</math> וסיבוכיותה היא מסדר גודל <math>O(n)</math>. היא אינה יעילה מהיבט קריפטוגרפי כיוון שאם <math>n</math> גדול (נניח באורך <math>n\ge 2^{128}</math> סיביות) התקפה כזו אינה פרקטית. שיטה מעט יותר טובה נקראת "צעד-קטן צעד-גדול" והיא מבוססת על העובדה שאם <math>\beta=\alpha^x</math> אפשר לכתוב את <math>x</math> בצורה: <math>x=im+j</math> (לפי כלל [[חילוק מודולרי|החילוק המודולרי]]) כאשר <math>j<m</math> ו-<math>m=\left\lceil\sqrt{n}\right\rceil</math>. לכן <math>\alpha^x=\alpha^{im}\alpha^j</math> לאחר העברת אגפים מתקבל <math>\beta(\alpha^{-m})^i=\alpha^j</math>. מהאמור עולה שאם מכינים טבלה המכילה את הזוגות (<math>j,\alpha^j</math>) עבור כל המספרים מ-1 עד <math>m</math>, הממויינת לפי האלמנט השני, מובטח שיימצא אלמנט אחד (אם קיים פתרון) השווה ל-<math>\beta(\alpha^{-m})^i</math>. היות שהטבלה היא בסדר גודל של השורש הריבועי של סדר החבורה וחיפוש בטבלה ממויינת אינו קשה, יוצא שסיבוכיות השיטה היא <math>O(\sqrt{n})</math> אך היא דורשת [[סיבוכיות מקום]] בסדר גודל של <math>O(\sqrt{n})</math> ועל כן אם <math>n</math> גדול מאוד (נניח <math>n\ge 2^{128}</math>) היא אינה פרקטית.
| |||