אלגוריתם פוליג-הלמן

300px|ממוזער|שמאל|שיטת פוליג הלמן
בתורת החבורות ובקריפטוגרפיה **אלגוריתם פוליג-הלמן** (באנגלית: Pohlig–Hellman algorithm) הוא אלגוריתם לפתרון בעיית הלוגריתם הבדיד במקרה הפרטי כאשר סדר החבורה הוא מספר חלק (שגורמיו הראשוניים קטנים). האלגוריתם הומצא ב-1978 על ידי סטיבן פוליג ומרטין הלמן.

## בעיית הלוגריתם הבדיד

בעיית הלוגריתם הבדיד הכללית היא: בהינתן חבורה ציקלית \mathbb{G} מסדר q ויוצר g ויהי h\in \mathbb{G} איבר כלשהו. מצא x המקיים h=g^x. הוא נקרא הלוגריתם הבדיד של h בבסיס g בקיצור \log_g h. אם q ראשוני, אלגוריתם צעד-קטן צעד-גדול פותר את הבעיה בסיבוכיות זמן של \sqrt{q} צעדים ובסיבוכיות מקום זהה. אלגוריתם רו של פולרד פותר את הבעיה בזמן דומה אך ללא צריכת זיכרון משמעותית.

בעיית הלוגריתם הבדיד נחשבת במקרה הכללי לבעיה קשה. האלגוריתם הטוב ביותר הידוע לפתרון הבעיה כאשר סדר החבורה הוא מספר ראשוני הוא אלגוריתם רו של פולרד המבוסס על אלגוריתם צעד-קטן צעד-גדול.

## רקע מתמטי
אלגוריתם פוליג הלמן מנסה להאיץ את חישוב הלוגריתם הבדיד במקרה שסדר החבורה q אינו ראשוני וידועים גורמים לא טריוויאליים שלו. ידוע שהסדר של האיבר g הוא השלם i הקטן ביותר המקיים g^i=1. יהי q הסדר של g ונניח שקיים שלם p שהוא מחלק שלו (p|q) אז הסדר של g^p הוא q/p. הכללה של משפט השאריות הסיני אומרת שאם ידוע הפירוק: \textstyle q=\Pi_{i=1}^k q_i כאשר כל q_i זר יחסית לגורמים האחרים (כלומר \text{gcd}(q_i,q_j)=1 עבור כל i\ne j) כאשר gcd היא מחלק משותף מקסימלי, אז קיימת התאמה או איזומורפיזם בין החבורות \mathbb{Z}_{q_i} למכפלה הקרטזית שלהם \mathbb{Z}_{q_1}\times\mathbb{Z}_{q_2}\times\cdots\times\mathbb{Z}_{q_k} וקיימת דרך יעילה לעבור בין הייצוגים השונים.

בהינתן היוצר g ואיבר כלשהו נניח h ואנחנו מעוניינים למצוא את x כך שמתקיים g^x=h, נניח שהסדר של g הוא q וידועים לנו הגורמים שלו: \textstyle q=\Pi_{i=1}^k q_i (הגורמים לא חייבים להיות ראשונים כל עוד הם זרים זה לזה), אז ידוע שמתקיים:
:(g^{q/q_i})^x=(g^x)^{q/q_i}=h^{q/q_i} עבור כל i=1,...,k.
אם g_i=g^{q/q_i} עבור כל i אז מתקבלות k בעיות של לוגריתם בדידי ב-k חבורות, כל אחת מסדר q_i שהסדר שלהן קטן משמעותית מ-q. אם נפתור את k המופעים הללו בעזרת כל אלגוריתם כוח גס לפתרון בעיית לוגריתם בדיד, נוכל לפתור את הבעיה בחבורה הגדולה (נובע ממשפט השאריות הסיני). כלומר הלוגריתמים הבדידיים x_i מ-1 עד k מקיימים: g_i^{x_i}=h^{q/q_i}=g_i^x. היות ש-x שקול ל-x_i מודולו q_i עבור כל i לפי משפט השאריות הסיני למערכת המשוואות הבאה:

יש פתרון יחיד x מודולו q. כך שאפשר לחשב אותו מתוך x_1,...,x_k עם אלגוריתם כמו אלגוריתם גאוס או אלגוריתם של גרנר (מתואר בהמשך).

## תיאור האלגוריתם
תיאור אלגוריתם פוליג-הלמן מתוך הספר "מבוא למתמטיקה של ההצפנה". תהי \mathbb{G} חבורה ונניח שיש לנו אלגוריתם לפתרון בעיית הלוגריתם הבדיד ב-\mathbb{G} עבור כל איבר מסדר שהוא חזקה ראשונית (מתואר בהמשך). למשל אם g\in\mathbb{G} הוא מסדר q^e ונניח שיש לנו אלגוריתם שפותר את הבעיה g^x=h בסיבוכיות של q^{e/2}. אם הסדר של g\in\mathbb{G} הוא N שניתן לפירוק מהצורה N=q_1^{e_1}\cdot q_2^{e_2}\cdots q_k^{e_k} אז אפשר לפתור את בעיית הלוגריתם הבדיד g^x=h בסיבוכיות של
:O(\sum_{i=1}^k q_i^{e_i/2}+\log N) צעדים.

השיטה היא כדלהלן:

#עבור i=1 עד k בצעו:
##g_i=g^{N/q_i^{e_i}} וכן h_i=h^{N/q_i^{e_i}}
##היות שכל g_i הוא מסדר חזקה ראשונית, אפשר להשתמש באלגוריתם לפתרון בעיית הלוגריתם הבדיד עם סדר מחזקה ראשונית שמתואר להלן, כתת-שגרה שלו, כדי לפתור את הבעיה g_i^y=h_i.
##יהי y=y_i הפתרון למשוואה זו.
#פותרים את מערכת המשוואות המודולרית בעזרת משפט השאריות הסיני:

אלגוריתם פוליג-הלמן בעצם מצמצם את בעיית הלוגריתם הבדיד של איבר מסדר כלשהו לבעיית הלוגריתם הבדיד של איבר מסדר שהוא חזקה של ראשוני. לכן בעיית הלוגריתם הבדיד בחבורה \mathbb{G} קלה לפתרון אם הסדר של החבורה הוא כפולה של ראשוניים קטנים. למשל במקרה של השדה \mathbb{F}_p אם p-1 מתפרק לגורמים קטנים אז לא מומלץ להשתמש בשדה הזה אם רוצים חבורה שבה הבעיה נחשבת קשה. מה שאפשר לעשות זה למצוא שדה כזה כך שהראשוני p שווה 2q+1 כאשר q ראשוני וכן לבחור יוצר מסדר q ואז עובדים בתת-חבורה מסדר q של \mathbb{F}_p וסיבוכיות פתרון בעיית הלוגריתם הבדיד בתת-חבורה זו יהיה מסדר O(\sqrt{q}). בגלל שאלגוריתם תחשיב אינדקסים הוא תת-מעריכי q צריך להיות גדול.

יתרה מזו אפשר לצמצם את בעיית הלוגריתם הבדיד של איבר מסדר חזקה ראשונית לסדר ראשוני בסיבוכיות O(e\sqrt{q}) (להיפטר מהחזקה). בגלל הטריק הבא: אם g הוא מסדר q^e אז g^{q^{e-1}} הוא מסדר q. אם חוזרים על פעולה זו מספר פעמים אפשר להגיע לפתרון הלוגריתם הבדיד. הרעיון הוא לכתוב את המעריך x בצורה:
:x=x_0+x_1q+x_2q^2+\cdots x_{e-1}q^{e-1} כאשר 0\le x_i.
ואז לחשב רקורסיבית את x_0,x_1,x_2,.... היות ש-g^{q^{e-1}} הוא מסדר q מזה נובע ש:

הראשון נובע מהעלאת שני האגפים של g^x=h בחזקת q^{e-1}. השני נובע מההצגה המורחבת של x השלישי נובע מהעובדה ש-g^{q^e}=1. לכן המשוואה:
:\left(g^{q^{e-1}}\right)^{x_0}=h^{q^{e-1}}
הוא לוגריתם בדיד שהבסיס שלו הוא איבר מסדר q. ההנחה היא שאפשר לפתור בעיה זו ב-\sqrt{q} צעדים. אם פתרנו את המשווה הזו נוכל למצוא את x_0 עם המאפיין:
:g^{x_0q^{e-1}}=h^{q^{e-1}} בחבורה \mathbb{G}.

בשלב הבא מבצעים חישוב דומה והפעם מעלים את שני האגפים של g^x=h בחזקת q^{e-2} ומקבלים את:

היות שאנחנו כבר יודעים את ערכו של x_0, כדי למצוא את x_1 אנחנו צריכים לחשב את הלוגריתם הבדיד
:\left(g^{q^{e-1}}\right)^{x_1}=\left(h\cdot g^{-x_0}\right)^{q^{e-2}}.
עבור הנעלם x_1. שוב אפשר עם האלגוריתם לפתרון לוגריתם בדיד מסדר ראשוני ב-\sqrt{q} צעדים למצוא את x_1 ואז קיבלנו את x_0 ו-x_1 המקיימים:
:g^{(x_0+x_1q)q^{e-2}}=h^{q^{e-2}} ב-\mathbb{G}.
באותה דרך אפשר למצוא את x_2, באופן כללי אחרי שאנחנו יודעים מהם הערכים של x_0,...,x_{i-1} אז אפשר לחשב את x_i על ידי פתרון:
:(g^{q^{e-1}})^{x_i}=(h\cdot g^{-x_0-x_1q-\cdots -x_{i-1}q^{i-1}})^{q^{e-i-1}} בחבורה \mathbb{G}. כל לוגריתם כזה ניתן לפתרון בזמן שורש q צעדים. לכן אחרי e\sqrt{q} צעדים אפשר לקבל את המעריך x=x_0+x_1q+\cdots + x_{e-1}q^{e-1} המקיים g^x=h.

### דוגמאות להמחשה
נתונים הערכים:
:p=11251, g=23, h=9689.
:N=(p-1)=q_1^{e_1}q_2^{e_2}q_3^{e_3}=2\cdot 3^2\cdot 5^4
והבעיה היא לפתור את המשוואה g^x=9689 בשדה \mathbb{F}_{11251}^* שהוא מסדר 11250. במקרה זה פותרים את הלוגריתם הבדיד של תת-בעיות מסדר נמוך לפי הגורמים הראשוניים של N. שני הגורמים הראשונים קטנים לכן הפתרון שלהם טריוויאלי. להלן דוגמה לפתרון בעיית הלוגריתם הבדיד בסדר של הגורם השלישי. אנחנו מנסים לפתור את המשוואה 5448^x=6909 בשדה \mathbb{F}_{11251}^*. היות שהראשוני p=11251 נבחר בצורה כזו ש-p-1 מתחלק ב-5^4 ולכן 5448 הוא מסדר 5^4 בשדה \mathbb{F}_{11251}^*. פותרים אותו בהדרגה כדי לקבל את x כדלהלן:

1. הצעד הראשון הוא לפתור את המשוואה (5448^{5^3})^{x_0}=6909^{5^3}, שמצטמצמת למשוואה 11089^{x_0}=11089 זה קל כי x_0=1 הוא הפתרון היחיד ובשלב זה ערכו של x הוא x=x_0=1.

2. בצעד השני מנסים לפתור את:
:\left(5448^{5^3}\right)^{x_1}=\left(6909\cdot 5448^{-x_0}\right)^{5^2}=\left(6909\cdot 5448^{-1}\right)^{5^2},
שמצטמצמת למשוואה 11089^{x_1}=3742.
כל מה שצריך לבדוק עבור x_1 זה ערכים בטווח 1 עד 4. כך שאפשר לפתור את זה בכוח גס די בקלות. במקרה זה הפתרון הוא x_1=2, לכן בשלב זה ערכו של x הוא x=11=1+2\cdot 5.

3. ממשיכים לצעד הבא ומנסים לפתור את:
:\left(5448^{5^3}\right)^{x_2}=\left(6909\cdot 5448^{-x_0-x_1\cdot 5}\right)^5=\left(6909 \cdot 5448^{-11}\right)^5,
שמצטמצמת למשוואה 11089^{x_2}=1 לכן x_2=0 והמשמעות במקרה זה היא שערכו של x נשאר 11 בשלב זה.

4. הצעד הבא והאחרון הוא לפתור את:
:\left(5448^{5^3}\right)^{x_3}=6909\cdot 5448^{-x_0-x_1\cdot 5-x_2\cdot 5^2}=6909\cdot 5448^{-11}.

5. התוצאה האחרונה היא 11089^{x_3}=6320, שהפתרון שלה הוא x_3=4 לכן התשובה הסופית היא:
:x=511=1+2\cdot 5+4\cdot 5^3.
:אפשר לראות שמתקיים 5448^{511}=6909 בשדה \mathbb{F}_{11251}^*.

להלן דוגמה לאלגוריתם פוליג הלמן המשתמש במשפט השאריות הסיני כדי לחבר ביחד את כל הפתרונות לפתרון השלם. בטבלה הבאה מוצגים פתרונות שלוש תת-הבעיות:

הבעיה המופיעה בשורה השלישית היא הבעיה מהדוגמה הקודמת.

בשלב זה מנצלים את משפט השאריות הסיני כדי לפתור את מערכת המשוואות המודולרית:

והפתרון הוא 23^{4261}=9689 מודולו 11251.

### אלגוריתם גרנר לפתרון CRT
אלגוריתם גרנר לפתרון מערכת משוואות מודלרית לפי משפט השאריות הסיני.

**קלט:** שלם חיובי m שהוא כפולה של t שלמים חיוביים זרים זה לזה m_1\cdot m_2\cdots m_t וייצוג מודולרי v(x)=(v_1,v_2,...,v_t) (השאריות) של x מודולו m_i בהתאמה.

**פלט:** שלם x המקיים את משוואת CRT.
# עבור i=2 עד t מצבעים:
##C_i=1
##עבור j=1 עד (i-1) מבצעים:
###u=m_j^{-1}\text{ mod }m_i
###C_i=u\cdot C_i\text{ mod }m_i
#u=v_1,x=u
#עבור i=2 עד t מחשבים את: u=(v_i-x)C_i\text{ mod }m_i,x=x+u\Pi_{j=1}^{i-1}m_j.
#מחזירים את x.

## הערות שוליים

קטגוריה:תורת המספרים
קטגוריה:קריפטוגרפיה
קטגוריה:אלגוריתמים