אלגוריתם פוליג-הלמן
ויקיפדיה האנציקלופדיה encyclopedia
בתורת החבורות ובקריפטוגרפיה אלגוריתם פוליג-הלמן (באנגלית: Pohlig–Hellman algorithm) הוא אלגוריתם לפתרון בעיית הלוגריתם הבדיד במקרה הפרטי כאשר סדר החבורה הוא מספר חלק (שגורמיו הראשוניים קטנים). האלגוריתם הומצא ב-1978 על ידי סטיבן פוליג ומרטין הלמן[1].
- ערך מורחב – בעיית הלוגריתם הבדיד
בעיית הלוגריתם הבדיד הכללית היא: בהינתן חבורה ציקלית מסדר ויוצר ויהי איבר כלשהו. מצא המקיים . הוא נקרא הלוגריתם הבדיד של בבסיס בקיצור . אם ראשוני, אלגוריתם צעד-קטן צעד-גדול פותר את הבעיה בסיבוכיות זמן של צעדים ובסיבוכיות מקום זהה. אלגוריתם רו של פולרד פותר את הבעיה בזמן דומה אך ללא צריכת זיכרון משמעותית.
בעיית הלוגריתם הבדיד נחשבת במקרה הכללי לבעיה קשה. האלגוריתם הטוב ביותר הידוע לפתרון הבעיה כאשר סדר החבורה הוא מספר ראשוני הוא אלגוריתם רו של פולרד המבוסס על אלגוריתם צעד-קטן צעד-גדול.
אלגוריתם פוליג הלמן מנסה להאיץ את חישוב הלוגריתם הבדיד במקרה שסדר החבורה אינו ראשוני וידועים גורמים לא טריוויאליים שלו. ידוע שהסדר של האיבר הוא השלם הקטן ביותר המקיים . יהי הסדר של ונניח שקיים שלם שהוא מחלק שלו () אז הסדר של הוא . הכללה של משפט השאריות הסיני אומרת שאם ידוע הפירוק: כאשר כל זר יחסית לגורמים האחרים (כלומר עבור כל ) כאשר gcd היא מחלק משותף מקסימלי, אז קיימת התאמה או איזומורפיזם בין החבורות למכפלה הקרטזית שלהם וקיימת דרך יעילה לעבור בין הייצוגים השונים.
בהינתן היוצר ואיבר כלשהו נניח ואנחנו מעוניינים למצוא את כך שמתקיים , נניח שהסדר של הוא וידועים לנו הגורמים שלו: (הגורמים לא חייבים להיות ראשונים כל עוד הם זרים זה לזה), אז ידוע שמתקיים:
- עבור כל .
אם עבור כל אז מתקבלות בעיות של לוגריתם בדידי ב- חבורות, כל אחת מסדר שהסדר שלהן קטן משמעותית מ-. אם נפתור את המופעים הללו בעזרת כל אלגוריתם כוח גס לפתרון בעיית לוגריתם בדיד, נוכל לפתור את הבעיה בחבורה הגדולה (נובע ממשפט השאריות הסיני). כלומר הלוגריתמים הבדידיים מ-1 עד מקיימים: . היות ש- שקול ל- מודולו עבור כל לפי משפט השאריות הסיני למערכת המשוואות הבאה:
|
יש פתרון יחיד מודולו . כך שאפשר לחשב אותו מתוך עם אלגוריתם כמו אלגוריתם גאוס או אלגוריתם של גרנר (מתואר בהמשך).