הצגת המקור של הדף "אלגוריתם rho של פולרד"

ב[[תורת המספרים]], '''אלגוריתם רו של פולרד''' (באנגלית:  Pollard's rho algorithm) הוא [[אלגוריתם הסתברותי]] ל[[פירוק מספר שלם לגורמים]], שפותח ב-[[1975]] על ידי [[ג'ון פולרד]]. האלגוריתם מוצא גורם ראשוני אחד, בדרך כלל את הקטן ביותר, וסיבוכיות הריצה שלו מסדר הגודל של שורש הגורם הראשוני. זאת בניגוד לאלגוריתם הפירוק הנאיבי מחד, שסיבוכיות הריצה שלו מסדר גודל של שורש המספר שאותו מבקשים לפרק, ולאלגוריתמים המודרניים לפירוק מאידך, שסיבוכיות הריצה שלהם תת-אקספוננציאלית בלוגריתם של המספר. ב-[[1981]] שימש האלגוריתם (בגרסה משופרת שלו) לפירוק [[מספר פרמה]] השמיני (כ-77 ספרות עשרוניות), ונמצא שיש לו גורם ראשוני קטן.

==חיפוש התנגשויות==
אלגוריתם rho של פולרד מבוסס על [[אלגוריתם פלויד למציאת מחזוריות]], המטפל בפונקציה <math>\ f : S \rightarrow S</math> מקבוצה סופית <math>\ S</math> אל עצמה. איבר התחלתי <math>\ x_0\in S</math> [[הגדרה איטרטיבית|מגדיר באינדוקציה]] את סדרת הערכים שהפונקציה מקבלת, <math>\ x_{n+1} = f(x_n)</math>. מכיוון שזו סדרה של ערכים בקבוצה סופית, היא מוכרחה לחזור על עצמה, והמסלול שהיא מתארת יהפוך למחזורי מאותו זמן והלאה. שיטת פולארד נקראת "שיטת <math>\ \rho</math>", בגלל צורת האות היוונית הדומה לתיאור סכמתי של המחזור.

[[עקרון שובך היונים]] מבטיח חזרה בתוך <math>\ n = |S|</math> צעדים, ולא פחות; עם זאת, אם הפונקציה f אקראית, אז [[פרדוקס יום הולדת]] מביא לחזרה בתוך זמן קצר בהרבה - <math>\ \sqrt{\pi n/2}+O(1)</math> צעדים, בתוחלת.

בעיית המחזוריות מבקשת למצוא [[התנגשות (מדעי המחשב)|התנגשות]] מפורשת; קרי, למצוא, ביעילות, אינדקסים <math>\ i\ne j</math> שעבורם <math>\ x_i=x_j</math>. הדרך הנאיבית היא לאחסן את הרצף <math>\ x_i</math> בזיכרון (למשל באמצעות [[פונקציית גיבוב|טבלת גיבוב]]) ולחפש בכל צעד כפילויות עם הערכים הקודמים. שיטה זו דורשת זיכרון מסדר הגודל של מספר הערכים שיתקבלו עד להתנגשות הראשונה, ובמקרים רבים זו דרישה בלתי מעשית. 

ב-[[1960]] פיתח [[רוברט פלויד]] אלגוריתם אלגנטי המוצא התנגשות תוך שימוש בזיכרון זניח בלבד: בחישוב סדרת הערכים, מחשבים במקביל גם את אותה סדרה במהירות כפולה. היינו, מתחילים בזוג ערכים <math>\ (x_0,x_0)</math>, ובכל צעד מחליפים את הזוג <math>\ (x_i,x_{2i})</math> בזוג 
<math>\ (x_{i+1},x_{2(i+1)}) = (f(x_i),f(f(x_{2i})))</math>, ומשווים את שני הרכיבים. ברגע שמתקבל השוויון <math>\ x_m=x_{2m}</math>, נמצאה התנגשות. 

== שימוש למציאת גורמים ==

כדי למצוא גורם ראשוני של מספר נתון n, הציע פולארד לבחור פונקציה אריתמטית כמו <math>\ f(x)=x^2+1</math>, המחושבת מנקודת התחלה אקראית מודולו n. ההיוריסטיקה קובעת שפונקציה כזו מתנהגת כמו פונקציה אקראית. בהתאם לאלגוריתם של פלויד, מחשבים שני רצפים במקביל, לאורך אותם ערכים, כשהאחד נע במהירות כפולה מחברו. השוואת בני הזוג <math>\ x_{2m},x_{m}</math> אינה מתבצעת מודולו n, אלא על ידי חישוב ה[[מחלק משותף מקסימלי|מחלק המשותף המרבי]] של <math>\ x_i-x_j</math> ו-<math>\ n</math>. הרעיון הוא שסדרת הערכים <math>\ x_i</math>, המחושבת מודולו n, '''מוגדרת''' מודולו כל גורם ראשוני p של n (גם אם p אינו ידוע), ולכן היא מהווה גם סדרה של ערכים במרחב של p השאריות בחלוקה ל-p. התנגשות במרחב הקטן הזה, שאמורה להתרחש בתוך <math>\ O(\sqrt{p})</math> צעדים, תזוהה מיד, מכיוון שההפרש באותו זמן יהיה 0 מודולו p, כך ש-p יחלק את המחלק המשותף המקסימלי <math>\ \operatorname{gcd}(n,x_{2m}-x_m)</math>. יש גם סיכוי לכך שההתנגשות תתרחש בו זמנית מודולו כל גורם (חזקת-)ראשוני של n, ואז המחלק המשותף המקסימלי יהיה n, והאלגוריתם נכשל.

==האלגוריתם==
גרסה בסיסית של אלגוריתם rho עם הפונקציה: <math>\ f(x)=x^2+1</math>.
# קבע <math>\ a = 2, b = 2</math>
# עבור <math>\ i = 1,2,...</math> בצע כדלהלן:
::א. חשב את: <math>\ a = (a^2+1) \mbox{ mod }n</math>.
::ב. חשב את <math>\ b = (b^2+1) \mbox{ mod }n</math> ושוב: <math>\ b = (b^2+1) \mbox{ mod }n</math>.
::ג. חשב את <math>\ d = \mbox{gcd}(|a-b|,n)</math> 
:::אם <math>\ d > 1</math> אזי <math>\ d</math> הוא גורם של <math>\ n</math> אחרת,
:::אם <math>\ d = n</math>, האלגוריתם מסתיים בכישלון.

'''הערה:''' הסיכויים ש-<math>\ d=n</math> אינם גבוהים, אך אם בכל זאת האלגוריתם מסתיים כאשר <math>\ d=n</math> ישנן מספר אפשרויות. אחת היא לחזור על האלגוריתם עם ערכים התחלתיים שונים. השנייה היא לחזור על האלגוריתם עם [[פולינום]] אחר, בעל מקדם חופשי גבוה מ-1 למשל <math>\ f(x)=x^2+c</math> אם <math>\ c\ne 0,-2</math>. 

בהנחה שהפונקציה <math>\ f(x)=(x^2+1) \mbox{ mod }p</math> מתנהגת כפונקציה אקראית, זמן הריצה המשוער של האלגוריתם הוא <math>\ O(\sqrt{p})</math> צעדים [[אריתמטיקה|אריתמטיים]] (של [[חשבון מודולרי|כפל מודולרי]]) ועל כן הזמן המשוער למציאת גורם לא טריוויאלי של <math>\ n</math> הוא <math>\ O(n^{1/4})</math>.

==דוגמה במספרים קטנים==
הטבלה הבאה מציגה את הלולאה הראשית (שלב 2) באלגוריתם בפירוק המספר <math>\ n = 206360731</math> : 

{| class="wikitable" border="1"
|-
!
! <math>\ a</math>
! <math>\ b</math>
! <math>\ \mbox{gcd}(|a-b|, n)</math>
|-
| <math>\ 1</math>
| <math>\ 5</math>
| <math>\ 26</math>
| <math>\ 1</math>
|- style="background-color: #EFEFEF;"
| <math>\ 2</math>
| <math>\ 26</math>
| <math>\ 458330</math>
| <math>\ 1</math>
|-
| <math>\ 3</math>
| <math>\ 677</math>
| <math>\ 41654832</math>
| <math>\ 1</math>
|- style="background-color: #EFEFEF;"
| <math>\ 4</math>
| <math>\ 458330</math>
| <math>\ 170662567</math>
| <math>\ 1</math>
|-
| <math>\ 5</math>
| <math>\ 197525474</math>
| <math>\ 129619099</math>
| <math>\ 167</math>
|}

נמצא ש-<math>\ 167</math> הוא אחד הגורמים, למעשה הגורם הקטן ביותר של <math>\ 206360731</math>. יתר הגורמים הם <math>\ 1409</math> ו-<math>\ 877</math>.

==גרסה משופרת של האלגוריתם==
[[ריצ'רד ברנט]] פרסם ב-[[1980]] גרסה משופרת של אלגוריתם rho המכונה אלגוריתם פירוק לגורמים מונטה קרלו משופר, המציע שיפור של כ-36 אחוז במקרה הממוצע, ביחס לאלגוריתם המקורי. במקום להשתמש באלגוריתם מחזוריות של פלויד כפי שעושה האלגוריתם של פולרד, אלגוריתם ברנט משתמש בשיטה שונה הנקראת back-tracking (נסיגה) כדי לאתר את מחזוריות הרצף ולמנוע חזרה מיותרת.

[[C (שפת תכנות)|קוד C]] של אלגוריתם מונטה קרלו של ברנט:
<syntaxhighlight lang="c">
int BrentPollard(int n, int x0, int m)
{
     int g, x, y = x0, ys, r = 1, q = 1;
     do{
         x = y;
         for(int i = 1; i < r; i++) 
         {
             y = f(y, n);
         }
         int k = 0; 
         do{ 
             ys = y;
             for(int j = 1; j < MIN(m, r-k); j++)
             {
                 y = f(y, n);
                 q = (q * ABS(x-y)) % n;
             }
             g = gcd(q, n);
             k += m;
         } while( k < r && g <= 1);
         r <<= 1;
     } while(g <= 1);
     if(g == n)
     {
         do{
             ys = f(ys, n);
             g = gcd(ABS(x - ys), n);
         } while(g <= 1); 
         if(g == n) return 0;
     }
     return g;
}
</syntaxhighlight>
הקלט: <math>\ n</math> הוא המספר המיועד לפירוק, <math>\ m</math> מספר אקראי כלשהו הנמוך מ-<math>\ n</math>, ו-<math>\ x_0</math> הוא ערך התחלתי כלשהו בדרך כלל 2. הפונקציה <math>\ \mbox{f(x,n)}</math> אמורה להיות פונקציה אקראית כלשהי מודולו <math>\ n</math>, כמו <math>\ f(x)=(x^2+3)\mbox{ mod }n</math>, המאקרו ABS מייצג [[ערך מוחלט]] והפונקציה gcd היא [[אלגוריתם אוקלידס]].

==יעילות==
אלגוריתם rho של פולרד מספק איזון הדדי בין זמן הריצה לבין סיכוי ההצלחה. במקרה הקשה כאשר המספר הוא כפולה של שני גורמים ראשוניים שווים בגודלם בערך, זמן ריצה משוער של <math>\ O(n^{1/4} \operatorname{polylog}(n))</math> צעדים, יניב גורם ראשוני בסיכויים של חצי בהערכה גסה (אף על פי שזוהי הערכה [[היוריסטיקה|היוריסטית]] בלבד). שאלת יעילות האלגוריתם המדויקת היא בעיה פתוחה.

אלגוריתם rho מהיר למדי עבור מספרים עם גורמים ראשוניים קטנים. למשל ב[[מחשב]] בינוני, יישום מעשי של האלגוריתם בפירוק מספר פרמה השישי (כעשרים ספרות עשרוניות) לוקח כמחצית שנייה. לעומת זאת לפירוק מספר בגודל זהה, שהוא כפולה של שני מספרים ראשוניים גדולים (לא בהכרח שונים) השווים בגודלם בקירוב, נדרשות כעשר שניות לפחות.

ההישג המשמעותי ביותר של האלגוריתם היה של גרסת ברנט המשופרת, איתה הצליחו ג'ון פולרד וריצ'רד ברנט לפרק את מספר פרמה השמיני <math>\ F_8=2^{2^8}+1</math> בזמן כולל של שעתיים על [[מחשב מרכזי]] מדגם [[UNIVAC]].


==ראו גם==
* [[פירוק לגורמים של מספר שלם]]
* [[אלגוריתם רו של פולרד ללוגריתמים]]

==לקריאה נוספת==
* המאמר של [http://wwwmaths.anu.edu.au/~brent/ ריצ'רד ברנט] [http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf An Improved Monte Carlo Factorization Algorithm]
* הספר [http://www.cacr.math.uwaterloo.ca/hac Handbook of Applied Cryptography], פרק 3.
* [[דונלד קנות']], '''The art of computer programming'''. Vol 2: Seminumerical Algorithms.

==קישורים חיצוניים==
* {{MathWorld}}

{{קריפטוגרפיה}}

[[קטגוריה:תורת המספרים]]
[[קטגוריה:מספרים ראשוניים]]
[[קטגוריה:שיטות פירוק לגורמים]]