אלגוריתם רו של פולרד ללוגריתם הבדיד – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 20:
בעיית דיפי-הלמן המסומנת בקיצור DHP, היא בעייה דומה שהועלתה לראשונה על ידי [[ויטפילד דיפי]] ו[[מרטין הלמן]] במאמר המפורסם שלהם שבו הציגו לראשונה את [[הצפנת מפתח ציבורי]] ו[[פרוטוקול שיתוף מפתח]] המבוסס על הבעיה הבאה: נתון המספר הראשוני <math>p</math> ויוצר <math>\alpha</math> של החבורה <math>\mathbb{Z}_p^*</math> וכן נתונים <math>\alpha^x</math> ו-<math>\alpha^y</math> (מודולו <math>p</math>). מצא את <math>\alpha^{xy}</math> מודולו <math>p</math>. בעיה זו נחשבת גם היא לבעיה קשה אם כי לא הוכח האם היא קשה לפחות כבעיית הלוגריתם הדיסקרטי. מאידך, כל דרך לפתרון בעיית הלוגריתם הדיקסרטי יכולה לשמש לפתרון בעיית דיפי-הלמן.
לדוגמה אם נתון המספר הראשוני <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>.
הבעיה נקראת לוגריתם '''בדידי''' בגלל שהיא עוסקת אך ורק במספרים שלמים [[מודולו]] שלם כלשהו הנקרא [[חשבון מודולרי|מודולוס]]. ראוי לציין שלמרות שקל לחשב לוגריתמים באופן כללי, אין הדבר נכון לגבי לוגריתם בדידי מכיוון שהתנהגות התוצאה נראית אקראית על פניה ולא ניתן לבצע [[קירוב]]. הסיבה שהבסיס הוא יוצר היא כדי שהחבורה תהיה ציקלית כך שכל אלמנט בחבורה ניתן לייצוג כחזקה של היוצר. הדרישה שהחבורה תהיה ציקלית אינה הכרחית, הגדרה כללית יותר של הבעיה, הנקראת בקיצור GDLP, היא מציאת אלמנט <math>x</math> המקיים <math>\alpha^x=\beta</math>, בהנחה שקיים, עבור האלמנטים <math>\alpha,\beta\in G</math> (כאשר <math>\alpha</math> אינו בהכרח יוצר). החבורה החיבורית הנוצרת על ידי עקום אליפטי כאשר הפעולה היא חיבור נקודות בעקום היא דוגמה לחבורה שבה בעיית הלוגריתם הדיסקרטי קשה. אחת הדרכים לפתור את הבעיה היא בעצם חישוב [[איזומורפיזם]] בין חבורות. אפילו אם שתי חבורות איזומורפיות זו לזו, אלגוריתם יעיל לפתרון בעיית הלוגריתם הבדידי בחבורה אחת, אינו בהכרח יעיל בחבורה השנייה. למשל כל חבורה כפלית ציקלית מסדר <math>n</math> איזומורפית לחבורה החיבורית הציקלית <math>\mathbb{Z}_n</math>. על כל פנים, בעוד שקיים אלגוריתם יעיל לחישוב לוגריתמים בחבורה החיבורית מעל המספרים השלמים מודולו מספר ראשוני, כלומר מציאת שלם המקיים <math>ax\equiv b\text{ (mod }n)</math>, לא ניתן ליישמו לפתרון הלוגריתם הבדידי בחבורה הכפלית.
| |||