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

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

שיטת פוליג הלמן

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

ערך מורחב – בעיית הלוגריתם הבדיד

בעיית הלוגריתם הבדיד הכללית היא: בהינתן חבורה ציקלית $\mathbb{𝔾}$ מסדר $q$ ויוצר $g$ ויהי $h\in \mathbb{𝔾}$ איבר כלשהו. מצא $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$. הכללה של משפט השאריות הסיני אומרת שאם ידוע הפירוק: $q={\mathrm{\Pi }}_{i=1}^k{q}_i$ כאשר כל $q_i$ זר יחסית לגורמים האחרים (כלומר $\text{gcd}(q_i,q_j)=1$ עבור כל $i\ne j$) כאשר gcd היא מחלק משותף מקסימלי, אז קיימת התאמה או איזומורפיזם בין החבורות ${\mathbb{\mathbb{Z}}}_{q_i}$ למכפלה הקרטזית שלהם ${\mathbb{\mathbb{Z}}}_{q_1}\times {\mathbb{\mathbb{Z}}}_{q_2}\times \cdots \times {\mathbb{\mathbb{Z}}}_{q_k}$ וקיימת דרך יעילה לעבור בין הייצוגים השונים.

בהינתן היוצר $g$ ואיבר כלשהו נניח $h$ ואנחנו מעוניינים למצוא את $x$ כך שמתקיים $g^x=h$, נניח שהסדר של $g$ הוא $q$ וידועים לנו הגורמים שלו: $q={\mathrm{\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\equiv x_1\text{ mod }{q}_1$ $⋮$ $x\equiv x_k\text{ mod }{q}_k$

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

תיאור האלגוריתם

תיאור אלגוריתם פוליג-הלמן מתוך הספר "מבוא למתמטיקה של ההצפנה". תהי $\mathbb{𝔾}$ חבורה ונניח שיש לנו אלגוריתם לפתרון בעיית הלוגריתם הבדיד ב-$\mathbb{𝔾}$ עבור כל איבר מסדר שהוא חזקה ראשונית (מתואר בהמשך). למשל אם $g\in \mathbb{𝔾}$ הוא מסדר $q^e$ ונניח שיש לנו אלגוריתם שפותר את הבעיה $g^x=h$ בסיבוכיות של $q^{e/2}$. אם הסדר של $g\in \mathbb{𝔾}$ הוא $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)$ צעדים.

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

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

$x\equiv y_1\text{ (mod }{q}_1^{e_1})$, $x\equiv y_2\text{ (mod }{q}_2^{e_2})$, $⋮$ $x\equiv y_k\text{ (mod }{q}_k^{e_k})$.

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

יתרה מזו אפשר לצמצם את בעיית הלוגריתם הבדיד של איבר מסדר חזקה ראשונית לסדר ראשוני בסיבוכיות $O(e\sqrt{q})$ (להיפטר מהחזקה). בגלל הטריק הבא: אם $g$ הוא מסדר $q^e$ אז $g^{q^{e-1}}$ הוא מסדר $q$. אם חוזרים על פעולה זו מספר פעמים אפשר להגיע לפתרון הלוגריתם הבדיד. הרעיון הוא לכתוב את המעריך $x$ בצורה:

$x=x_0+x_{1}q+x_2{q}^2+\cdots x_{e-1}{q}^{e-1}$ כאשר $0\le x_i<q$.

ואז לחשב רקורסיבית את $x_0,x_1,x_2,...$. היות ש-$g^{q^{e-1}}$ הוא מסדר $q$ מזה נובע ש:

$h^{q^{e-1}}={\left(g^x\right)}^{q^{e-1}}$ $={\left(g^{x_0+x_{1}q+x_2{q}^2+\cdots +x_{e-1}{q}^{e-1}}\right)}^{q^{e-1}}$ $=g^{x_0{q}^{e-1}}\cdot {\left(g^{q^e}\right)}^{x_1+x_{2}q+\cdots +x_{e-1}{q}^{e-2}}$ $={\left(g^{q^{e-1}}\right)}^{x_0}$

הראשון נובע מהעלאת שני האגפים של $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_0{q}^{e-1}}=h^{q^{e-1}}$ בחבורה $\mathbb{𝔾}$.

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

$h^{q^{e-2}}={\left(g^x\right)}^{q^{e-2}}$ $={\left(g^{x_0+x_{1}q+x_2{q}^2+\cdots +x_{e-1}{q}^{e-1}}\right)}^{q^{e-2}}$ $=g^{x_0{q}^{e-2}}\cdot g^{x_1{q}^{e-1}}\cdot (g^{q^e}{)}^{x_2+x_{3}q+\cdots +x_{e-1}{q}^{e-3}}$ $=g^{x_0{q}^{e-2}}\cdot g^{x_1{q}^{e-1}}$.

היות שאנחנו כבר יודעים את ערכו של $x_0$, כדי למצוא את $x_1$ אנחנו צריכים לחשב את הלוגריתם הבדיד

${\left(g^{q^{e-1}}\right)}^{x_1}={(h\cdot g^{-x_0})}^{q^{e-2}}$.

עבור הנעלם $x_1$. שוב אפשר עם האלגוריתם לפתרון לוגריתם בדיד מסדר ראשוני ב-$\sqrt{q}$ צעדים למצוא את $x_1$ ואז קיבלנו את $x_0$ ו-$x_1$ המקיימים:

$g^{(x_0+x_{1}q)q^{e-2}}=h^{q^{e-2}}$ ב-$\mathbb{𝔾}$.

באותה דרך אפשר למצוא את $x_2$, באופן כללי אחרי שאנחנו יודעים מהם הערכים של $x_0,...,x_{i-1}$ אז אפשר לחשב את $x_i$ על ידי פתרון:

$(g^{q^{e-1}}{)}^{x_i}=(h\cdot g^{-x_0-x_{1}q-\cdots -x_{i-1}{q}^{i-1}}{)}^{q^{e-i-1}}$ בחבורה $\mathbb{𝔾}$. כל לוגריתם כזה ניתן לפתרון בזמן שורש $q$ צעדים. לכן אחרי $e\sqrt{q}$ צעדים אפשר לקבל את המעריך $x=x_0+x_{1}q+\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{𝔽}}_{11251}^{*}$ שהוא מסדר 11250. במקרה זה פותרים את הלוגריתם הבדיד של תת-בעיות מסדר נמוך לפי הגורמים הראשוניים של $N$. שני הגורמים הראשונים קטנים לכן הפתרון שלהם טריוויאלי. להלן דוגמה לפתרון בעיית הלוגריתם הבדיד בסדר של הגורם השלישי. אנחנו מנסים לפתור את המשוואה $5448^x=6909$ בשדה ${\mathbb{𝔽}}_{11251}^{*}$. היות שהראשוני $p=11251$ נבחר בצורה כזו ש-$p-1$ מתחלק ב-$5^4$ ולכן $5448$ הוא מסדר $5^4$ בשדה ${\mathbb{𝔽}}_{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}={(6909\cdot 5448^{-x_0})}^{5^2}={(6909\cdot 5448^{-1})}^{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}={(6909\cdot 5448^{-x_0-x_1\cdot 5})}^5={(6909\cdot 5448^{-11})}^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{𝔽}}_{11251}^{*}$.

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

$q$	$e$	$g^{N/q^e}$	$h^{N/q^e}$	$(g^{N/q^e}{)}^x=h^{N/q^e}$
2	1	11250	11250	1
3	2	5029	10724	4
5	4	5448	6909	511

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

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

$x\equiv 1\text{ (mod }2)$ $x\equiv 4\text{ (mod }{3}^2)$ $x\equiv 511\text{ (mod }{5}^4)$

והפתרון הוא $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.

1. עבור $i=2$ עד $t$ מצבעים:
   1. $C_i=1$
   2. עבור $j=1$ עד $(i-1)$ מבצעים:
      1. $u=m_j^{-1}\text{ mod }{m}_i$
      2. $C_i=u\cdot C_i\text{ mod }{m}_i$
2. $u=v_1,x=u$
3. עבור $i=2$ עד $t$ מחשבים את: $u=(v_i-x)C_i\text{ mod }{m}_i,x=x+u{\mathrm{\Pi }}_{j=1}^{i-1}{m}_j$.
4. מחזירים את $x$.