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

בתורת המספרים ובקריפטוגרפיה, אלגוריתם רו של פולרד ללוגריתם הדיסקרטי (באנגלית: Pollard’s rho algorithm for discrete logarithms) הוא אלגוריתם הסתברותי לחישוב לוגריתם בדיד בחבורה ציקלית סופית מסדר ראשוני עם זמן ריצה דומה לשיטת כוח גס גנרית הנקראת אלגוריתם צעד-קטן צעד-גדול אך עם צריכת זיכרון שולית ביחס אליה. האלגוריתם פותר את בעיית הלוגריתם הבדיד בהסתברות גבוהה, בסיבוכיות בסדר גודל של $O({\sqrt {n}})$ כאשר $n$ הוא סדר החבורה. לצורך אלגוריתם פולרד ההנחה היא שסדר החבורה הוא מספר ראשוני, שאם לא כן, אפשר בשילוב עם אלגוריתם פוליג-הלמן לפתור את בעיית הלוגריתם הבדיד בזמן ריצה שהוא בסדר גודל $O({\sqrt {p}})$ כאשר $p$ הוא הגורם הראשוני הגדול ביותר של $n$.

היסטוריה

צורת האות היוונית "רו" של מיפוי אקראי

אלגוריתם רו הומצא על ידי המתמטיקאי הבריטי ג'ון פולרד והתפרסם במאמר "שיטת מונטה קרלו לחישוב אינדקסים" בכתב העת המדעי "Mathematics of Computation" ביולי 1978. בדומה לאלגוריתם רו של פולרד לפירוק לגורמים הוא נקרא בשם זה בשל העובדה שבמיפוי אקראי (או הילוך מקרי) בקבוצה סופית, נוצר מעין "מעגל" אליו מחובר "שובל" קצר וצורתו דומה במקצת לאות היוונית $\rho$ (כמתואר בתרשים משמאל), כלומר בהינתן פונקציה אקראית לאחר מספר מוגבל של ערכים מגיעים לנקודה בה הערכים מתחילים לחזור על עצמם במעגל אין סופי. הרעיון של פולרד ניתן להרחבה לכל סוג של חבורה ציקלית, כמו חבורה אבלית מעל עקום אליפטי הידועה בפופולריות שלה בהצפנה המודרנית ולמעשה לא ידוע על אלגוריתם שמציג סיבוכיות טובה יותר לפתרון בעיית הלוגריתם הבדיד בעקום אליפטי. בחבורה ציקלית מעל מספר ראשוני קיים אלגוריתם תחשיב אינדקסים עם זמן ריצה תת-מעריכי והוא נחשב ליעיל ביותר הידוע כיום למספרים גדולים אך אינו בר ביצוע בעקום אליפטי.

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

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

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

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

בעיית הלוגריתם הבדיד המסומנת בקיצור DLP היא כדלקמן:

נתונה חבורה ציקלית סופית מסדר $n$ המסומנת $G$ ונתון יוצר $\alpha$ של החבורה ויהי $\beta \in G$ אלמנט כלשהו. מצא את הלוגריתם הבדיד של $\beta$ בבסיס $\alpha$ בקיצור $\log _{\alpha }\beta$ שהוא אלמנט יחיד $x$ בטווח $0\leq x\leq n-1$ המקיים: $\beta =\alpha ^{x}$.

בעיית דיפי-הלמן בקיצור DHP, היא בעיה דומה שהועלתה לראשונה על ידי ויטפילד דיפי ומרטין הלמן במאמר המפורסם שלהם שבו הציגו לראשונה את הצפנת מפתח ציבורי ופרוטוקול שיתוף מפתח המבוסס על הבעיה הבאה: נתון המספר הראשוני $p$ ויוצר $\alpha$ של החבורה $\mathbb {Z} _{p}^{*}$ וכן נתונים $\alpha ^{x}$ ו-$\alpha ^{y}$ (מודולו $p$). מצא את $\alpha ^{xy}$ מודולו $p$. בעיה זו נחשבת גם היא לבעיה קשה אם כי לא הוכח האם היא קשה לפחות כבעיית הלוגריתם הבדיד. מאידך, כל דרך לפתרון בעיית הלוגריתם הדיקסרטי יכולה לשמש לפתרון בעיית דיפי-הלמן.

לדוגמה אם נתון המספר הראשוני $p=97$ החבורה $\mathbb {Z} _{97}^{*}$ היא חבורה ציקלית מסדר $n=96$. יוצר אפשרי אחד של חבורה זו יכול להיות $\alpha =5$. (קל לראות שאם מעלים את 5 בחזקת כל המספרים מ-1 עד 96 (מודולו 97) מתקבלים כל האלמנטים של החבורה בלי יוצא מן הכלל לא בהכרח לפי סדר עולה). אם נבחר $x=32$ בחשבון פשוט מתקבל $5^{32}\equiv 35{\text{ (mod }}97)$ לכן $\log _{5}35=32$ בחבורה $\mathbb {Z} _{97}^{*}$. וכן, אם $y=17$ אז $5^{17}\equiv 83{\text{ (mod }}97)$. אם נתונים האלמנטים $5^{32}\equiv 35$ ו-$5^{17}\equiv 83$ (מודולו 97) בעיית דיפי-הלמן היא לגלות את $5^{32\cdot 17}\equiv 61{\text{ (mod }}97)$ (כשהאלמנטים $x$ ו-$y$ אינם ידועים).

הבעיה נקראת לוגריתם בדיד כיוון שהיא עוסקת בקבוצה סופית מודולו שלם כלשהו הנקרא מודולוס. ראוי לציין שאף-על-פי שקל לחשב לוגריתמים באופן כללי, אין הדבר נכון לגבי לוגריתם בדיד מכיוון שהתנהגות התוצאה נראית אקראית על פניה ולא ניתן לבצע קירוב. הסיבה שהבסיס הוא יוצר היא כדי שהחבורה תהיה ציקלית כך שכל אלמנט בחבורה ניתן לייצוג כחזקה של היוצר. הדרישה שהחבורה תהיה ציקלית אינה הכרחית, הגדרה כללית יותר של הבעיה, הנקראת בקיצור GDLP, היא מציאת אלמנט $x$ המקיים $\alpha ^{x}=\beta$, בהנחה שקיים, עבור האלמנטים $\alpha ,\beta \in G$ (כאשר $\alpha$ אינו בהכרח יוצר). החבורה החיבורית הנוצרת על ידי עקום אליפטי כאשר הפעולה היא חיבור נקודות בעקום היא דוגמה לחבורה שבה בעיית הלוגריתם הבדיד קשה. אחת הדרכים לפתור את הבעיה היא בעצם חישוב איזומורפיזם בין חבורות. אפילו אם שתי חבורות איזומורפיות זו לזו, אלגוריתם יעיל לפתרון בעיית הלוגריתם הבדיד בחבורה אחת, אינו בהכרח יעיל בחבורה השנייה. למשל כל חבורה כפלית ציקלית מסדר $n$ איזומורפית לחבורה החיבורית הציקלית $\mathbb {Z} _{n}$. על כל פנים, בעוד שקיים אלגוריתם יעיל לחישוב לוגריתמים בחבורה החיבורית מעל המספרים השלמים מודולו מספר ראשוני, כלומר מציאת שלם המקיים $ax\equiv b{\text{ (mod }}n)$, לא ניתן ליישמו לפתרון הלוגריתם הבדיד בחבורה הכפלית.

הדרך הישירה והפשוטה ביותר לפתרון בעיית הלוגריתם הבדיד היא שיטת כוח גס, סריקת כל החזקות של $\alpha$ בזה אחר זה מ-1 עד $n$ עד שמתקבל $\beta$ וסיבוכיותה היא מסדר גודל $O(n)$. היא אינה יעילה מהיבט קריפטוגרפי כיוון שאם $n$ גדול (נניח באורך $n\geq 2^{128}$ סיביות) התקפה כזו אינה פרקטית. שיטה מעט יותר טובה נקראת "צעד-קטן צעד-גדול" והיא מבוססת על העובדה שאם $\beta =\alpha ^{x}$ אפשר לכתוב את $x$ בצורה: $x=im+j$ (לפי כלל החילוק המודולרי) כאשר $j<m$ ו-$m=\left\lceil {\sqrt {n}}\right\rceil$. לכן $\alpha ^{x}=\alpha ^{im}\alpha ^{j}$ לאחר העברת אגפים מתקבל $\beta (\alpha ^{-m})^{i}=\alpha ^{j}$. מהאמור עולה שאם מכינים טבלה המכילה את הזוגות ($j,\alpha ^{j}$) עבור כל המספרים מ-1 עד $m$, הממויינת לפי האלמנט השני, מובטח שיימצא אלמנט אחד (אם קיים פתרון) השווה ל-$\beta (\alpha ^{-m})^{i}$. היות שהטבלה היא בסדר גודל של השורש הריבועי של סדר החבורה וחיפוש בטבלה ממויינת אינו קשה, יוצא שסיבוכיות השיטה היא $O({\sqrt {n}})$ אך היא דורשת סיבוכיות מקום בסדר גודל של $O({\sqrt {n}})$ ועל כן אם $n$ גדול מאוד (נניח $n\geq 2^{128}$) היא אינה פרקטית.

תיאור כללי

אלגוריתם רו של פולרד מנסה לייצר "סדרה פסידו-אקראית" של אלמנטים מהחבורה בהתבסס על רעיון מונטה קרלו וחיפוש אחר התנגשויות, כלומר שני אלמנטים זהים בסדרה. אם נמצאה התנגשות הדבר מוביל לפתרון בעיית הלוגריתם הבדיד בהסתברות גבוהה. שני רעיונות מרכזיים של פולרד הם פונקציה איטרטיבית אקראית קלה לחישוב, איתה מכינים את הסדרה הפסאודו-אקראית ואלגוריתם מציאת מחזוריות שמנסה למצוא בה התנגשות בזמן הקצר ביותר ללא שימוש בטבלאות. לצורך הפשטות נניח שנתונה חבורה ציקלית $G$ מסדר $n$ ראשוני.

תחילה מחלקים את $G$ לשלוש קבוצות בגודל זהה בקירוב $S_{1},S_{2},S_{3}$, בחלוקה לוגית בהתבסס על כלל מנחה קל לבדיקה. אפשר למשל לחלק לפי משקלו של כל אלמנט באופן הבא הקבוצה $S_{1}$ תכיל את כל האלמנטים: $\textstyle 0<x_{i}<{\frac {1}{3}}n$, הקבוצה $S_{2}$ את האלמנטים $\textstyle {\frac {1}{3}}n<x_{i}<{\frac {2}{3}}n$ והשלישית $\textstyle {\frac {2}{3}}n<x_{i}<n$. דרך אחרת יותר יעילה היא לחלק לפי הערך של $t$ הסיביות הכי פחות משמעותיות של כל $x_{i}$ כאשר $t$ תלוי במספר החלוקות (במקרה זה מספיק לבחון את שתי הסיביות האחרונות). מספר החלוקות שרירותי וניתן לשינוי, אך יש צורך לשים לב לכמה היבטים חשובים בנוגע לחלוקה למשל $1\notin S_{2}$.

מחשבים סדרה פסידו-אקראית של אלמנטים מהחבורה לפי הכלל הבא. בוחרים אלמנט התחלתי $x_{0}=1$ ועבור כל $i\geq 0$ מחשבים:

$x_{i+1}=f(x_{i}){\overset {\underset {\mathrm {def} }{}}{=}}{\begin{cases}\beta \cdot x_{i},&{\mbox{ if }}x_{i}\in S_{1}\\x_{i}^{2},&{\mbox{ if }}x_{i}\in S_{2}\\\alpha \cdot x_{i},&{\mbox{ if }}x_{i}\in S_{3}\end{cases}}$

בנוסף מתוך הסדרה האמורה מכינים שתי רשימות של שלמים $a_{0},a_{1},a_{2},...$ וכן $b_{0},b_{1},b_{2},...$ כאשר $a_{0}=0$ ו-$b_{0}=0$ ועבור כל $i\geq 0$ מחשבים את

$a_{i+1}={\begin{cases}a_{i},&{\mbox{ if }}x_{i}\in S_{1}\\2a_{i}{\text{ mod }}n,&{\mbox{ if }}x_{i}\in S_{2}\\a_{i}+1{\text{ mod }}n,&{\mbox{ if }}x_{i}\in S_{3}\end{cases}}$

וכן

$b_{i+1}={\begin{cases}b_{i}+1{\text{ mod }}n,&{\mbox{ if }}x_{i}\in S_{1}\\2b_{i}{\text{ mod }}n,&{\mbox{ if }}x_{i}\in S_{2}\\b_{i},&{\mbox{ if }}x_{i}\in S_{3}\end{cases}}$

הערכים של $a_{i}$ ו-$b_{i}$ מחושבים כך שעבור כל $i$ מתקיים $x_{i}=\alpha ^{a_{i}}\cdot \beta ^{b_{i}}$. אם $x_{i}=x_{j}$ כאשר $i\neq j$ זה אומר שנמצאה "התנגשות". כדי למצוא התנגשות ביעילות האלגוריתם מנצל טכניקה המיוחסת לרוברט פלויד (לפי דונלד קנות') שנקראת מציאת מחזוריות או "שיטת הצב והארנב" שהיא שיטה יעילה לאיתור מחזוריות של פונקציה איטרטיבית אקראית על עצמה מהצורה $f:X\rightarrow X$. מנסים באופן רקורסיבי לאתר את הנקודה בה הסדרה מתחילה לחזור על עצמה. מבצעים בכל איטרציה שתי הליכות, הליכה איטית והליכה מהירה. בהליכה איטית מחשבים מתוך הערכים מהאיטרציה הקודמת את השלשה החדשה ($x_{i},a_{i},b_{i}$) ובהליכה מהירה את $(x_{2i},a_{2i},b_{2i})$ ומשווים בין $x_{i}$ ל-$x_{2i}$, אם הם שווים אותרה מחזוריות הפונקציה וזה אומר שמנקודה זו ואילך המסלול יחזור על עצמו במעגל אין סופי. סיבוכיות הטכניקה הזו זהה לשיטה הישירה המסתמכת על חיפוש בטבלאות ומבזבזת זיכרון רב. אם נמצאה התאמה המשמעות היא ש-$\alpha ^{a_{i}}\beta ^{b_{i}}=\alpha ^{a_{2i}}\beta ^{b_{2i}}$ ולכן $\beta ^{b_{i}-b_{2i}}=\alpha ^{a_{2i}-a_{i}}$. אם לוקחים לוגריתם בבסיס $\alpha$ של שני האגפים במשוואה האחרונה מתקבל

$(b_{i}-b_{2i})\cdot \log _{\alpha }\beta \equiv (a_{2i}-a_{i}){\text{ (mod }}n)$.

בהנחה ש-$b_{i}\not \equiv b_{2i}{\text{ (mod }}n)$, שבכל מקרה עלול לקרות בהסתברות מאוד זניחה. מתוך המשוואה האחרונה אפשר לחלץ את $\log _{\alpha }\beta$ על ידי הכפלה בהופכי הכפלי של $(b_{i}-b_{2i})$.

פירוט מהלכי האלגוריתם

אלגוריתם רו של פולרד

קלט: החבורה $G$ מסדר $n$, יוצר $\alpha$ והאלמנט $\beta$.

פלט: הלוגריתם הבדיד $x=\log _{\alpha }\beta$.

1. מציבים $x_{0}=1,a_{0}=0,b_{0}=0$.
2. מבצעים לולאה עם $i=1,2,3,...$
   1. מחשבים את הערכים של $x_{i},a_{i},b_{i}$ מתוך הערכים הקודמים $x_{i-1},a_{i-1},b_{i-1}$ וכן $x_{2i-2},a_{2i-2},b_{2i-2}$ לפי הנוסחאות המתוארות לעיל.
   2. אם $x_{i}=x_{2i}$ מבצעים:
      1. מציבים $r=b_{i}-b_{2i}{\text{ mod }}n$
      2. אם $r=0$ אלגוריתם מסתיים בכישלון אחרת מחזירים את $x=r^{-1}(a_{2i}-a_{i}){\text{ mod }}n$.

במקרה הנדיר שהאלגוריתם מסתיים בכישלון מגרילים $a_{0},b_{0}$ אחרים ומתחילים מההתחלה כאשר $x_{0}=\alpha ^{a_{0}}\beta ^{b_{0}}$.

דוגמה במספרים קטנים

נתונה תת-חבורה $G$ של החבורה $\mathbb {Z} _{383}^{*}$ מסדר $n=191$ עם היוצר $\alpha =2$ ונתון $\beta =228$. חלוקת האלמנטים של $G$ לשלוש קבוצות מתבצעת לפי הכלל הבא: מחשבים את $x{\text{ mod }}3$, אם השארית 1 הוא שייך ל-$S_{1}$, אם השארית היא 0 הוא שייך ל-$S_{2}$ ואילו אם השארית היא 2 הוא שייך ל-$S_{3}$. הטבלה הבאה מסכמת את מהלכי האלגוריתם והערכים של $x_{i},a_{i},b_{i}$ וכן $x_{2i},a_{2i},b_{2i}$ לאחר כל איטרציה. באיטרציה ה-14 נמצאה התנגשות כי $x_{14}=x_{28}=144$. לכן מחשבים את $r=38-104=125{\text{ (mod }}191)$ וההופכי שלו $125^{-1}\equiv 136{\text{ (mod }}191)$ ולכן $136\cdot (10-12)\equiv 110{\text{ (mod }}191)$ והפתרון הוא $\log _{2}228=110$ מודולו 191.

$i$	$x_{i}$	$a_{i}$	$b_{i}$	$x_{2i}$	$a_{2i}$	$b_{2i}$
1	228	0	1	279	0	2
2	279	0	2	184	1	4
3	92	0	4	14	1	6
4	184	1	4	256	2	7
5	205	1	5	304	3	8
6	14	1	6	121	6	18
7	28	2	6	144	12	38
8	256	2	7	235	48	152
9	152	2	8	72	48	154
10	304	3	8	14	96	118
11	372	3	9	256	97	119
12	121	6	18	304	98	120
13	12	6	19	121	5	51
14	144	12	38	144	10	104

אלגוריתם רו של פולרד בעקום אליפטי

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

נתון עקום אליפטי $E$ המוגדר מעל השדה $\mathbb {F} _{q}$, נתונה נקודה $P\in E(\mathbb {F} _{q})$ מסדר $n$ ונקודה $Q\in \langle P\rangle$, מצא שלם $l$ בטווח $[0,n-1]$ המקיים $Q=lP$.

השלם $l$ נקרא הלוגריתם הבדיד של הנקודה $Q$ בבסיס הנקודה $P$ או בקיצור $l=\log _{P}Q$. אם הפרמטרים של העקום $E$ נבחרו בזהירות כדי להבטיח שלא יהיו קיצורי דרך לפתרון הבעיה בעקום זה, הדרך הטובה ביותר לפתרונה היא באמצעות אלגוריתם רו של פולרד בסיבוכיות של ${\sqrt {n}}$. הסימון $\langle P\rangle$ מייצג את כל הנקודות שהן כפולות של $P$. (כגון $P,2P,3P,4P,...$ וכן הלאה עד $n$). במילים אחרות, הנקודה $Q$ היא תוצאה של חיבור הנקודה $P$ בעצמה (הנקראת בקיצור POINT_DBL) בדיוק $l$ פעמים והבעיה היא לגלות כמה פעמים בוצע החיבור, קרי לגלות את ערכו של $l$. לא קיימת דרך פשוטה לבצע זאת כי המסלול של הנקודות נראה אקראי. שיטת כוח גס אינה מעשית משום שבמקרה הממוצע יש צורך לבדוק לפחות מחצית מהנקודות עד שנמצא $lP$. אם $n\geq 2^{128}$ כוח גס אינו מעשי. כמובן שיש לשים לב של-$n$ יש לפחות גורם ראשוני אחד גדול דיו. שאם לא כן אפשר לנצל את אלגוריתם פוליג-הלמן בזמן שהוא ביחס ישיר לגודל הגורמים הראשוניים שלו. למעשה ככל שהגורם הראשוני שלו (לפחות אחד מהם) גדול יותר סיבוכיות ההתקפה תהיה גבוהה יותר.

תיאור כללי

כמו בחבורה ציקלית, הרעיון של אלגוריתם רו בעקום אליפטי הוא למצוא שני זוגות שלמים ($c,d$) וכן ($e,f$) מודולו $n$ המקיימים:

$cP+dQ=eP+fQ$

ואז

$(c-e)P=(f-d)Q=(f-d)lP$

ולכן

$(c-e)\equiv (f-d)l{\text{ (mod }}n)$

מזה נובע שאפשר לחשב את $l=\log _{P}Q$ על ידי $l=(c-e)(f-d)^{-1}{\text{ mod }}n$.

הדרך הישירה למצוא זוגות המקיימים את המשוואה האמורה היא על ידי בחירה אקראית ואחסון בטבלה. אם מכינים טבלה המכילה את כל השלשות: ($c,d,cP+dQ$) וממיינים לפי הערך השלישי, מובטח שבסופו של דבר הערך הזה יופיע פעם נוספת מה שיאפשר לגלות את הלוגריתם הבדיד כאמור. תופעה שבה הערך השלישי מופיע פעמיים כאשר הערכים האחרים שונים נקראת "התנגשות". לפי פרדוקס יום ההולדת מספר הניסיונות הצפוי לפני שתופיע התנגשות הוא בערך $\textstyle {\sqrt {\pi n/2}}$ שזה בערך $\textstyle 1.2533{\sqrt {n}}$. אולם החסרון בשיטה זו הוא שיש צורך בזיכרון רב, ליתר דיוק $\textstyle {\sqrt {\pi n/2}}$ שלשות. אלגוריתם רו מנסה להימנע משימוש בזיכרון על ידי שיטת הצב והארנב. מגדירים פונקציה איטרטיבית אקראית $\langle P\rangle \rightarrow \langle P\rangle$ כך שבהינתן $X\in \langle P\rangle$ והערכים $c$ ו-$d$ כך שמתקיים $X=cP+dQ$ יהיה קל לחשב את ${\overline {X}}=f(X)$ ואת ${\overline {c}},{\overline {d}}$ כך שמתקיים ${\overline {X}}={\overline {c}}P+{\overline {d}}Q$.

לדוגמה, אם מחלקים את החבורה הציקלית $\langle P\rangle$ ל-$L$ רשימות בגודל זהה בקירוב (למשל $L=32$), מציבים כל נקודה $X_{i}$ ברשימה המתאימה $S_{j}$ אם הערך של 5 הסיביות הכי פחות משעותיות של הקואורדינטה $x$ של הנקודה $X_{i}$ הוא $j-1$. נניח ששיטת חלוקה זו תסומן ב-$H(X)$ ונניח שהערכים $a_{j}$ ו-$b_{j}$ הם שלמים אקראיים כלשהם הנמוכים מ-$n$ כאשר $j$ מתפרס על פני כל הרשימות של $L$, במקרה זה פונקציה אקראית איטרטיבית יכולה להיות:

$f(X)=X+a_{j}P+b_{j}Q$ כאשר $j=H(X)$

ולכן אם $X=cP+dQ$ אז הפונקציה האקראית היא $f(X)={\overline {X}}={\overline {c}}P+{\overline {d}}Q$ כאשר ${\overline {c}}=c+a_{j}{\text{ mod }}n$ וכן ${\overline {d}}=d+b_{j}{\text{ mod }}n$. כל נקודה התחלתית $X_{0}\in \langle P\rangle$ מגדירה סדרה אחרת $\{X_{i}\}_{i\geq 0}$ של נקודות כאשר כל נקודה מחושבת על ידי הנקודה הקודמת, $X_{i}=f(X_{i-1})$. היות שהחבורה הזו סופית בהכרח שתיגרם התנגשות, כלומר ערך של $X_{i}$ כלשהו יופיע שוב ומנקודה זו ואילך הסדרה תחזור על עצמה במעגל אין סופי. כלומר יופיע האינדקס הקטן ביותר $t$ המקיים $X_{t}=X_{t+s}$עבור $s$ כלשהו ומכאן ואילך $X_{i}=X_{i-s}$ עבור כל $i\geq t+s$. כאן $t$ הוא אורך השובל ו-$s$ הוא היקף מעגל במונחים של מספר האיטרציות של הפונקציה האיטרטיבית האקראית. אם $f$ היא פונקציה אקראית אז ההתנגשות הראשונה צפויה לקרות לאחר $\textstyle {\sqrt {\pi n/2}}$ צעדים בקירוב. אורך השובל הוא $\textstyle t\approx {\sqrt {\pi n/8}}$ ואורך המעגל צריך להיות $\textstyle s\approx {\sqrt {\pi n/8}}$ בקירוב.

התנגשות היא מצב שבו $X_{i}=X_{j}$ כאשר $i\neq j$ ואותה אפשר למצוא ללא צורך בזיכרון באמצעות שיטת פלויד או שיטת הצב והארנב. בשיטה זו מחשבים בכל צעד את הנקודות $X_{i}$ ו-$X_{2i}$ ומנסים למצוא התאמה. מספר הזוגות הצפוי שיש לבדוק הוא לכל הפחות $t$ זוגות ולכל היותר $t+s$ זוגות, עד שתמצא התנגשות. ליתר דיוק בהנחה ש-$f$ אקראית מספר הזוגות הצפוי שצריך לבדוק עד שתמצא התנגשות הוא $\textstyle k=1.0308{\sqrt {n}}$. מספר החישובים שיש לבצע בעקום האליפטי הוא בערך $\textstyle 3{\sqrt {n}}$ פעולות חיבור נקודות.

פירוט מהלכי האלגוריתם

אלגוריתם רו של פולרד לחישוב לוגריתם בדיד בעקום אליפטי.

קלט: הנקודה $P\in E(\mathbb {F} _{q})$ מסדר $n$ והנקודה $Q\in \langle P\rangle$

פלט: הלוגריתם הבדיד $l=\log _{P}Q$.

1. תחילה בוחרים את מספר הענפים או רשימות $L$ ואת פונקציית החלוקה $H$ שמציבה כל נקודה ברשימה המתאימה לפי הכלל $j$.
2. עבור $j=1$ עד $L$ מבצעים:
   1. מגרילים שני שלמים $a_{j},b_{j}$ ומחשבים את $R_{j}=a_{j}P+b_{j}Q$.
3. מגרילים זוג שלמים נוספים $c,d$ ומחשבים את $X'=cP+dQ$.
4. מציבים $X''=X',e=c,f=d$.
5. חוזרים על המהלכים הבאים:
   1. $j=H(X')$
   2. $X'=X'+R_{j},c=c+a_{j},d=d+b_{j}{\text{ (mod }}n)$.
   3. עבור $i=1$ עד 2 מבצעים:
      1. $j=H(X'')$
      2. $X'=X'+R_{j},c=c$
      3. $X''=X''+R_{j},e=e+a_{j},f=f+b_{j}{\text{ (mod }}n)$.
   4. עד שמתקבל $X'=X''$.
6. אם $d=f$ האלגוריתם הסתיים בכישלון, אחרת מחזירים את $l=(c-e)(f-d)^{-1}{\text{ mod }}n$.

דוגמה במספרים קטנים

נתון העקום $E(\mathbb {F} _{229})$ עם המשוואה $E:y^{2}=x^{3}+x+44$. נקודה $P=(x,y)=(5,116)$ היא מסדר ראשוני $n=239$. תהי הנקודה $Q=(155,166)\in \langle P\rangle$. כדי למצוא את $l=\log _{P}Q$ מגדירים תחילה $L=4$ ובוחרים פונקציית חלוקה $H:\langle P\rangle \rightarrow \{1,2,3,4\}$ לפי הכלל:

$H(x,y)=(x{\text{ mod }}4)+1$

בוחרים ומחשבים ארבע שלשות:

$[a_{1},b_{1},R_{1}]=[79,163,(135,117)]$

$[a_{2},b_{2},R_{2}]=[206,19,(96,97)]$

$[a_{3},b_{3},R_{3}]=[87,109,(84,62)]$

$[a_{4},b_{4},R_{4}]=[219,68,(72,134)]$

הטבלה הבאה מציגה את השלשות ($c,d,X'$) ו-($e,f,X''$) המתקבלות לאחר הצעד הרביעי באלגוריתם עבור המקרה $(c,d)=(54,175)$.

$i$	$c$	$d$	$X$	$c$	$d$	$X$
–	54	175	(39,159)	54	175	(39,159)
1	34	4	(160,9)	113	167	(130,182)
2	113	167	(130,182)	180	105	(36,97)
3	200	37	(27,17)	0	97	(108,89)
4	180	105	(36,97)	46	40	(223,153)
5	20	29	(119,180)	232	127	(167,57)
6	0	97	(108,89)	192	24	(57,105)
7	79	21	(81,168)	139	111	(185,227)
8	46	40	(223,153)	193	0	(197,92)
9	26	108	(9,18)	140	87	(194,145)
10	232	127	(167,57)	67	120	(223,153)
11	212	195	(75,136)	14	207	(167,57)
12	192	24	(57,105)	213	104	(57,105)

אפשר לראות בשורה האחרונה בטבלה שהאלגוריתם מצא התנגשות כי:

$192P+24Q=213P+104Q$

לכן

$l=(192-213)\cdot (104-24)^{-1}{\text{ mod }}239=176$.

שיפורים

בגלל הפופולריות של עקומים אליפטיים בקריפטוגרפיה, נעשה מאמץ לשפר את אלגוריתם רו של פולרד בין היתר על ידי עיבוד מקבילי. נניח שזמינים $M$ מחשבים לצורך פתרון הבעיה. הדרך הנאיבית היא להריץ את האלגוריתם על כל מחשב בנפרד עם נקודות התחלה אקראיות שונות, עד שאחד מהם יגלה התנגשות. שיטה זו אינה מנצלת את פוטנציאל המקביליות כי השיפור בביצועים הוא בפקטור ${\sqrt {M}}$ לכל היותר. פול ואן-אורשוט ומייקל ויינר הציעו גרסה מקבילית של אלגוריתם רו שמניבה שיפור בביצועים בפקטור של $M$. הרעיון הוא לאפשר לכל הסדרות $\{X_{i}\}_{i\geq 0}$ של כל המעבדים להתנגש אחת עם השנייה. ביתר פירוט, כל מעבד בוחר לעצמו נקודת התחלה $X_{0}$ באופן אקראי בנפרד מהאחרים, אולם כל המעבדים משתמשים באותה פונקציה איטרטיבית כדי לחשב את האלמנט הבא בסדרה $X_{i+1}$. לכן, אם נוצרת התנגשות בין שתי סדרות, כל הנקודות של שתי הסדרות החל בנקודה שבה הופיעה התנגשות תהיינה זהות. כדי להתאים את אלגוריתם פלויד למציאת מחזוריות בין סדרות נפרדות שנוצרות על ידי מעבדים שונים, נוקטים באסטרטגיה הבאה, בוחרים מאפיין ייחודי קל לזיהוי המשמש כ"נקודה מובחנת" (Distinguished Point). נקודה מובחנת יכולה להיות כזו המכילה למשל רצף של $t$ אפסים מובילים בקואורדינטה $x$ שלה. בכל פעם שמעבד נתקל בנקודה מובחנת כזו הוא משדר את הנקודה לשרת מרכזי שאוסף את כל הנקודות המובחנות מכל המעבדים וממיין אותם בזיכרון. אם השרת מקבל בשלב כלשהו נקודה מובחנת שכבר התקבלה קודם לכן, הוא מחשב את הלוגריתם הבדיד ומסיים בהצלחה.

אם הפרופורציה של הנקודות המובחנות ב-$\langle P\rangle$ היא $\theta$ הסיכויים לקבל התנגשות הם בערך $1/\theta$ לכן מספר פעולות כפל נקודות בעקום הצפוי מכל מעבד עד שמתקבלת התנגשות אחת הוא

${\frac {1}{M}}{\sqrt {\frac {\pi n}{2}}}+{\frac {1}{\theta }}$.

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

דרך נוספת לשפר ביצועים היא על ידי שימוש באוטומורפיזם. יהי $\psi :\langle P\rangle \rightarrow \langle P\rangle$ אוטומורפיזם של חבורה, כאשר $P$ היא נקודה בעקום מסדר $n$. בהנחה שקל לחשב את $\psi$ והיא מסדר $t$. כלומר $t$ הוא השלם הקטן ביותר כך ש-$\psi ^{t}(R)=R$ עבור כל $R$ ב-$\langle P\rangle$. מגדירים יחס שקילות על $\langle P\rangle$ המסומן $\sim$ על ידי

$R_{1}\sim R_{2}$ אם ורק אם $R_{1}=\psi ^{j}(R_{2})$ עבור $j$ בטווח $[0,t-1]$. מחלקת השקילות [R] היא

$[R]=\{R,\psi (R),\psi ^{2}(R),...,\psi ^{l-1}(R)\}$

כאשר $l$ הוא המחלק הקטן ביותר של $t$ המקיים $\psi ^{l}(R)=R$. הרעיון בהאצת האלגוריתם הוא לשנות את פונקציית האיטרציה $f$ שתהיה מעל מחלקת השקילות $[R]$. כדי לעשות זאת מגדירים הצגה קנונית של ${\overline {R}}$ של כל מחלקת שקילות $[R]$. למשל ${\overline {R}}$ יכולה להיות הנקודה ב-$[R]$ שהקואורדינטה $x$ שלה היא השלם הקטן ביותר. או למשל העתקת השלילה $\psi (P)=-P$. שאז אפשר להגדיר את פונקציית האיטרציה $g$ על ידי

$g(R)={\overline {f(R)}}$.

אם נניח שקיים שלם $\lambda$ המקיים $\psi (P)=\lambda P$ אז, היות ש-$\psi$ היא אוטומורפית מתקבל $\psi (R)=\lambda R$ עבור כל $R\in \langle P\rangle$. אם מוצאים שני שלמים $a,b$ המקיימים $X=aP+bQ$ אז אפשר לחשב בקלות את השלמים $a',b'$ המקיימים ${\overline {X}}=a'P+b'Q$. אם ${\overline {X}}=\psi ^{j}(X)$ אז $a'=\lambda ^{j}a{\text{ mod }}n$ וכן $b'=\lambda ^{j}b{\text{ mod }}n$. הפונקציה $g$ כאן משמשת כפונקציה איטרטיבית באלגוריתם רו בגרסה המקבילית שלו עם $M$ מעבדים. הנקודה התחלתית של כל סדרה היא $X_{0}'={\overline {X_{0}}}$ כאשר $X_{0}=a_{0}P+b_{0}Q$ ו-$a_{0},b_{0}$ הם שלמים אקראיים הנמוכים מ-$n$. הנקודות הבאות בכל סדרה מחושבות על ידי $X_{i}'=g(X_{i-1}')$. אם רוב מחלקות השקילות של $\langle P\rangle$ הן באורך $t$ אז טווח החיפוש מצטמצם ל-$n/t$ ולכן זמן הרצוי המשוער של האלגוריתם בגרסה משופרת זו הוא

${\frac {1}{M}}{\sqrt {\frac {\pi n}{2t}}}+{\frac {1}{\theta }}$.

זהו שיפור בפקטור של ${\sqrt {t}}$ במהירות הביצוע. אם משתמשים בהעתקת השלילה $\psi (P)=-P$ כאוטומורפיזם, מושג שיפור בפקטור של ${\sqrt {2}}$.

במקרה של עקום קובליץ $E_{a}$ מעל $\mathbb {F} _{2}$ שהוא עקום פופולרי בתקנים של NIST וסרטיקום, העתקת פרובניוס $\tau :E_{a}(\mathbb {F} _{2^{m}})\rightarrow E_{a}(\mathbb {F} _{2^{m}})$ המוגדרת על ידי $\tau ({\mathcal {O}})={\mathcal {O}}$ וכן $\tau (x,y)=(x^{2},y^{2})$ גם היא אוטומורפיזם של חבורה מסדר $m$ והיא קלה לחישוב היות שהעלאה בריבוע היא פעולה קלה בשדה הבינארי (בהצגה פולינומית העלאה בריבוע מודולו 2 שקולה למעשה להכנסת אפסים בין כל הספרות לסירוגין). אם $P\in E_{a}$ הוא מסדר ראשוני $n$ כך ש-$n^{2}$ אינו מחלק של סדר העקום המסומן ב-$\#E_{a}$ אז $\tau (P)\in \langle P\rangle$ ולכן $\tau$ היא אוטומורפית. יהי $\mu =(-1)^{1-a}$ אפשר להוכיח שאחד מהפתרונות $\lambda$ של המשוואה המודולרית $\lambda ^{2}-\mu \lambda +2\equiv 0{\text{ (mod }}n)$ מקיים $\tau (P)=\lambda P$. לכן באופן דומה, הגרסה המקבילית של אלגוריתם רו עם $M$ מעבדים המשתמשת במחלקות השקילות תחת העתקת פרובניוסמגיעה לזמן ריצה של

${\frac {1}{M}}{\sqrt {\frac {\pi n}{2m}}}+{\frac {1}{\theta }}$.

ואם מנצלים גם את העתקת השלילה מושג שיפור כולל בזמן הריצה בפקטור של ${\sqrt {2m}}$.

למשל ההערכה המקורית שניתנה ב-1996 הייתה שכדי לפתור את בעיית הלוגריתם הבדיד בעקום אליפטי מסדר 113 בהנחה שזמינים 10,000 מעבדים לצורך המשימה כשכל אחד מהם מסוגל לבצע איטרציה אחת בעשר מילישניות, אם $\theta =2^{-30}$ אז מספר החזרות הצפוי בכל מעבד לפני שמוצאים לוגריתם הוא

${\frac {\sqrt {\pi 2^{113}}}{2\cdot 10000}}+2^{30}\approx 9.03\times 10^{13}$.

שזה שקול בערך ל-1045 ימים או שלוש שנות עיבוד עם כמות של כארבע גיגה-בית זיכרון. הערכות יותר מעודכנות קצת יותר אופטימיות. לדוגמה ב-2002 הצליח צוות חוקרים בראשות קריס מוניקו לפצח את העקום האליפטי ECCp-109 עם 10,000 מחשבים שעבדו במקביל בסך הכול 549 ימים. הם השתמשו בגרסה משופרת של אלגוריתם רו של פולרד והצליחו לפתור את בעיית דיפי-הלמן בעקום זה.

לקריאה נוספת

• Hankerson, Darrel, Menezes, Alfred J., Vanstone, Scott (2004) Guide to Elliptic Curve Cryptography

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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