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

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

חיפוש התנגשויות

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

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

בעיית המחזוריות מבקשת למצוא התנגשות מפורשת; קרי, למצוא, ביעילות, אינדקסים $\ i\neq j$ שעבורם $\ x_{i}=x_{j}$ . הדרך הנאיבית היא לאחסן את הרצף $\ x_{i}$ בזיכרון (למשל באמצעות טבלת גיבוב) ולחפש בכל צעד כפילויות עם הערכים הקודמים. שיטה זו דורשת זיכרון מסדר הגודל של מספר הערכים שיתקבלו עד להתנגשות הראשונה, ובמקרים רבים זו דרישה בלתי מעשית.

ב-1960 פיתח רוברט פלויד אלגוריתם אלגנטי המוצא התנגשות תוך שימוש בזיכרון זניח בלבד: בחישוב סדרת הערכים, מחשבים במקביל גם את אותה סדרה במהירות כפולה. היינו, מתחילים בזוג ערכים $\ (x_{0},x_{0})$ , ובכל צעד מחליפים את הזוג $\ (x_{i},x_{2i})$ בזוג $\ (x_{i+1},x_{2(i+1)})=(f(x_{i}),f(f(x_{2i})))$ , ומשווים את שני הרכיבים. ברגע שמתקבל השוויון $\ x_{m}=x_{2m}$ , נמצאה התנגשות.

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

כדי למצוא גורם ראשוני של מספר נתון n, הציע פולארד לבחור פונקציה אריתמטית כמו $\ f(x)=x^{2}+1$ , המחושבת מנקודת התחלה אקראית מודולו n. ההיוריסטיקה קובעת שפונקציה כזו מתנהגת כמו פונקציה אקראית. בהתאם לאלגוריתם של פלויד, מחשבים שני רצפים במקביל, לאורך אותם ערכים, כשהאחד נע במהירות כפולה מחברו. השוואת בני הזוג $\ x_{2m},x_{m}$ אינה מתבצעת מודולו n, אלא על ידי חישוב המחלק המשותף המרבי של $\ x_{i}-x_{j}$ ו- $\ n$ . הרעיון הוא שסדרת הערכים $\ x_{i}$ , המחושבת מודולו n, מוגדרת מודולו כל גורם ראשוני p של n (גם אם p אינו ידוע), ולכן היא מהווה גם סדרה של ערכים במרחב של p השאריות בחלוקה ל-p. התנגשות במרחב הקטן הזה, שאמורה להתרחש בתוך $\ O({\sqrt {p}})$ צעדים, תזוהה מיד, מכיוון שההפרש באותו זמן יהיה 0 מודולו p, כך ש-p יחלק את המחלק המשותף המקסימלי $\ \operatorname {gcd} (n,x_{2m}-x_{m})$ . יש גם סיכוי לכך שההתנגשות תתרחש בו זמנית מודולו כל גורם (חזקת-)ראשוני של n, ואז המחלק המשותף המקסימלי יהיה n, והאלגוריתם נכשל.

האלגוריתם

גרסה בסיסית של אלגוריתם rho עם הפונקציה: $\ f(x)=x^{2}+1$ .

קבע $\ a=2,b=2$
עבור $\ i=1,2,...$ בצע כדלהלן:

א. חשב את:

\ a=(a^{2}+1){\mbox{ mod }}n

.

ב. חשב את

\ b=(b^{2}+1){\mbox{ mod }}n

ושוב:

\ b=(b^{2}+1){\mbox{ mod }}n

.

ג. חשב את

\ d={\mbox{gcd}}(|a-b|,n)

אם

\ d>1

אזי

\ d

הוא גורם של

\ n

אחרת,

אם

\ d=n

, האלגוריתם מסתיים בכישלון.

הערה: הסיכויים ש- $\ d=n$ אינם גבוהים, אך אם בכל זאת האלגוריתם מסתיים כאשר $\ d=n$ ישנן מספר אפשרויות. אחת היא לחזור על האלגוריתם עם ערכים התחלתיים שונים. השנייה היא לחזור על האלגוריתם עם פולינום אחר, בעל מקדם חופשי גבוה מ-1 למשל $\ f(x)=x^{2}+c$ אם $\ c\neq 0,-2$ .

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

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

הטבלה הבאה מציגה את הלולאה הראשית (שלב 2) באלגוריתם בפירוק המספר $\ n=206360731$ :

	$\ a$	$\ b$	$\ {\mbox{gcd}}(\|a-b\|,n)$
$\ 1$	$\ 5$	$\ 26$	$\ 1$
$\ 2$	$\ 26$	$\ 458330$	$\ 1$
$\ 3$	$\ 677$	$\ 41654832$	$\ 1$
$\ 4$	$\ 458330$	$\ 170662567$	$\ 1$
$\ 5$	$\ 197525474$	$\ 129619099$	$\ 167$

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

גרסה משופרת של האלגוריתם

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

קוד 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;
}

הקלט: $\ n$ הוא המספר המיועד לפירוק, $\ m$ מספר אקראי כלשהו הנמוך מ- $\ n$ , ו- $\ x_{0}$ הוא ערך התחלתי כלשהו בדרך כלל 2. הפונקציה $\ {\mbox{f(x,n)}}$ אמורה להיות פונקציה אקראית כלשהי מודולו $\ n$ , כמו $\ f(x)=(x^{2}+3){\mbox{ mod }}n$ , המאקרו ABS מייצג ערך מוחלט והפונקציה gcd היא אלגוריתם אוקלידס.

יעילות

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

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

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