ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
שורה 15:
|-
|
:'''נתונה חבורה ציקלית סופית מסדר <math>n</math> המסומנת כאן <math>G</math> ונתון [[ייצוג של חבורה|יוצר]] <math>\alpha</math> של החבורה ויהי <math>\beta\in G</math> אלמנט כלשהו. הלוגריתם הבדידי של <math>\beta</math> בבסיס <math>\alpha</math> בקיצור <math>\log_{\alpha} \beta</math> הוא אלמנט יחידי <math>x</math> בטווח <math>0\le x\le n-1</math> המקיים: <math>\beta=\alpha^x</math>.'''
|}
 
בעיית דיפי-הלמן המסומנת בקיצור 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>.
אוחזר מתוך "https://he.wikipedia.org/wiki/אלגוריתם_רו_של_פולרד_ללוגריתם_הבדיד"