נפת שדה מספרים

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

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

סיבוכיות

עם הופעתן של מערכת ההצפנה הא-סימטרית RSA, המבוססת על הקושי שבפירוק מספרים גדולים לגורמים, עלה קרנה של בעיה זו בתורת המספרים היישומית. בבעיית פירוק מספר נתון $n$ , גודל הקלט מורכב ממספר הספרות הבינאריות ומסומן $\log(n)$ . סיבוכיות פולינומית היא מהצורה $\log(n)^{c}$ עבור קבוע $c$ כלשהו גדול מ-0. לעומת זאת סיבוכיות אקספוננטית היא מהצורה $n^{c}=2^{c\cdot \log(n)}$ ; אלגוריתם בעל סיבוכיות כזו נחשב בדרך כלל לגרוע במיוחד. לא ידוע כיום על אלגוריתם בעל סיבוכיות פולינומית לבעיית הפירוק והעוסקים בתחום מעריכים שאלגוריתם כזה כלל אינו קיים. למעשה, עד להמצאתה של הנפה הריבועית, כל האלגוריתמים לבעיית הפירוק היו אקספוננטיים.

סיבוכיות פירוק $n$ לגורמים באמצעות שיטת הנפה הריבועית מוערכת ב-$L_{n}[{\tfrac {1}{2}},c]$ , כאשר

$L_{n}[\alpha ,c]=2^{c\log(n)^{\alpha }\log {\bigl (}\log(n)^{1-\alpha }{\bigr )}}$

היא פונקציית הסיבוכיות המתאימה לאלגוריתמים מסוג זה. $\alpha$ הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל-$\alpha$ הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של $\alpha$ , הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש-$c$ גדול יותר. לשם השוואה, $L_{n}[1,c]=n^{c}$ היא סיבוכיות אקספוננטית, בעוד ש-$L_{n}[0,c]=\log(n)^{c}$ היא סיבוכיות פולינומית. על סולם זה, הסיבוכיות של הנפה הריבועית נמצאת ב"אמצע הדרך" בין סיבוכיות אקספוננטית לפולינומית, והיא כאמור הראשונה שפרצה את מחסום האקספוננטיות. משך זמן רב עמדה בעיית הפירוק על סיבוכיות של $L_{n}[{\tfrac {1}{2}},c]$ והושגו רק שיפורים מינוריים בערכו של הקבוע $c$ .

פריצת הדרך ארעה ב-1988, כאשר המתמטיקאים ג'ון פולארד, מארק מאנאס, הנדריק לנסטרה וארג'ן לנסטרה פרסמו את שיטת "נפת שדה המספרים המיוחדת", שנועדה לפירוק מספרים בעלי מבנה מיוחד, כזה של מספרי פרמה ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה $L_{n}[{\tfrac {1}{3}},c]$ כשהקבוע $c=2{\sqrt[{3}]{\left({\tfrac {2}{3}}\right)^{2}}}\approx 1.526$ . כמספר שנים לאחר מכן, פותח האלגוריתם הכללי – "נפת שדה המספרים הכללית", המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-$L_{n}[{\tfrac {1}{3}},c]$ , כשהקבוע $c={\frac {4}{\sqrt[{3}]{9}}}\approx 1.923$ . בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות – אך אינן מוכחות.

לידתה של נפת שדה המספרים

הרעיון של נפת שדה המספרים החל עם עבודתם של דון קופרסמיט, אנדרו אודליצקו וריצ'רד שרופל, שניסו באמצע שנות התשעים לפתור את בעיית הלוגריתם הדיסקרטי באמצעות אלגוריתם שדה המספרים הריבועיים (Quadratic Number Field). הרעיון צד את עינו של פולרד שהציע ב-1988 לנצל את האלגוריתם גם לפירוק לגורמים של מספרים מהצורה $x^{3}-k$ כאשר $|k|$ קטן בשיטה שכונתה שדה מספרים אלגבריים. תחילה נוסה האלגוריתם בהצלחה בפירוק המספר $2F_{7}=x^{3}+2$ כאשר $x=2^{43}$ . מאוחר יותר הרחיבו האחים לנסטרה, מאנאס ופולארד עצמו את האלגוריתם לפירוק מספרים מהצורה $r^{e}\pm s$ כאשר $r$ הוא שלם חיובי קטן ו-$|s|$ קטן. מספרים אילו נקראים מספרי קנינגהם (Cunningham), האלגוריתם כונה נפת שדה מספרים מיוחדת (SNFS), יישום זה של האלגוריתם שימש בפירוק מספר פרמה התשיעי $F_{9}=2^{512}+1$ (בסדר גודל של 155 ספרות עשרוניות), שהתגלה ככפולה של שלושה מספרים ראשוניים.

הגרסה הכללית של האלגוריתם פותחה ושופצה על ידי מתמטיקאים רבים בראשם ג'ו בוהלר, ארג'ן לנסטרה, קארל פומרנץ דון קופרסמיט ורבים אחרים. קופרסמיט הציע שיפורים אחדים שייעלו את האלגוריתם לזמן של $L_{n}[1/3,2.007]$ ומקום בסדר גודל $L_{n}[1/3,1.639]$ . מאוחר יותר דווח צוות מתמטיקאים בראשות ברנשטיין ולנסטרה שהפעילו את האלגוריתם באופן מקבילי עם 16,384 מעבדים ופרקו בהצלחה מספר בגודל 119 ספרות עשרוניות בזמן קצר יחסית. קצב השיפור רק עלה במרוצת השנים. לנסטרה הכריז על הצלחתו לפרק באמצעות האלגוריתם, מודולוס RSA (ממספרי האתגר של מעבדות RSA), בגודל 130 ספרות עשרוניות. בנובמבר 2005 שימש האלגוריתם בהצלחה לפירוק המודולוס RSA-200 (בגודל 200 ספרות עשרוניות) גם הוא ממספרי האתגר. זהו המספר הגדול ביותר שפורק לגורמים נכון להיום. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל.

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

מספרי פרמה ומספרי קנינגהם

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

הבעיה הורחבה לבעיה כללית יותר של פירוק מספרים מהצורה $\ b^{m}\pm 1$ (כאשר $\ b$ קטן ו-$\ m$ גדול), מספרים אילו מכונים מספרי קנינגהם על שם המתמטיקאי אלן ג'וזף קנינגהם (Allan J. C. Cunningham). פרויקט קנינגהם הווה כעין מבחן כח להתקדמות בתחום הכללי של פירוק לגורמים. ב-1880 מצאו מתמטיקאים את הגורמים הראשוניים של $\ F_{6}$, רק כמאה שנים לאחר מכן ב-1970 הצליחו מוריסון וברילהרט לפרק את $\ F_{7}$ באמצעות שברים משולבים. מספר פרמה השמיני פורק ב-1980 על ידי ברנט ופולרד באמצעות גרסה של אלגוריתם rho של פולרד היעיל במיוחד במציאת גורמים קטנים. מספר פרמה התשיעי פורק לחלוטין ב-1990 על ידי האחים לנסטרה, מאנאס ופולרד שעשו זאת במאמץ שנמשך כארבעה חודשים, באמצעות נפת שדה המספרים והשתמשו בכח חישוב של כשבע מאות מחשבים שגויסו ממקומות שונים ברחבי העולם ומחשב-על אחד שריכז את העבודה. מספר פרמה העשירי פורק לגורמים ב-1999 על ידי ריצ'רד ברנט באמצעות שיטת העקום האליפטי . ב-1988 נעשה שימוש באותה שיטה כדי לפרק לגורמים את $\ F_{11}$ (שגורמיו הראשוניים נמצאו כולם קטנים). גורמים ראשוניים אחדים של מספרי פרמה מסוימים עד $\ F_{32}$ נמצאו גם הם, אך פירוקם המלא של מספרים אילו לגורמים טרם צלח.

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

שיטת הנפה הריבועית

ערך מורחב – נפה ריבועית

מלבד חלוקה נסיונית (Trial Division) הנאיבית, כל שיטות הפירוק הידועות כיום מבוססות על רעיון אחד: כדי לפרק את המספר $\ n$, יש לאתר זוג ריבועים, השקולים זה לזה מודולו $\ n$. אם $\ y^{2}\equiv x^{2}{\pmod {n}}$ ו- $\ y\not \equiv \pm x{\pmod {n}}$, אז $\ {\mbox{gcd}}(x-y,n)$ הוא גורם לא טריוויאלי של $\ n$ (gcd מסמן את המחלק המשותף המקסימלי).

אם $\ n$ פריק והמספרים $\ x$ ו-$\ y$ (או לפחות אחד מהם) אקראיים וריבועיהם שקולים מודולו $\ n$, הסיכוי לכך ש-$\ y\equiv \pm x{\pmod {n}}$ אינו עולה על חצי; לכן מספיק לאתר פתרונות למשוואה $\ y^{2}\equiv x^{2}{\pmod {n}}$ האמורה, ובמקרה של כישלון לנסות לאתר זוג אחר. הדרך להשיג זוג כזה הוצעה לראשונה על ידי דיקסון ונוסתה לראשונה במסגרת שיטת הנפה הריבועית. היא מבוססת על כך שגם אם קשה לפרק את $\ n$, ישנם מספרים שקל לפרקם, אלו שכל גורמיהם קטנים יחסית (וניתנים לניחוש). בוחרים "בסיס" המורכב מן הראשוניים הקטנים $\ F=\{p_{1},p_{2},...,p_{m}\}$ ומספר שכל גורמיו נמצאים ב-$\ F$ נקרא "F-חלק". כעת מחפשים באקראי מספרים $\ r_{i}$, כך ש-$\ f(r_{i})=r_{i}^{2}-n$ הוא מספר חלק ביחס ל-$\ F$. מכיוון שהפירוק של כל אחד מהמספרים $\ f(r_{i})$ ידוע, אפשר לחפש מכפלות של מספרים כאלה, השוות בעצמן לריבוע. חיפוש זה נעשה באמצעות דירוג של מטריצת המעריכים שהתקבלה מן הפירוקים השונים, מודולו 2, וחיפוש תלות לינארית בין וקטורי המעריכים. אותה מכפלה $\ f(r_{i_{1}})\cdots f(r_{i_{k}})$ היא, מחד, מכפלה של גורמים ראשוניים שכל אחד מהם מופיע מספר זוגי של פעמים, ומאידך שקולה מודולו $\ n$ לריבוע של $\ r_{i_{1}}\cdots r_{i_{k}}$. כך מתקבל זוג הריבועים המבוקש.

אלגוריתם נפת שדה המספרים משתמש ברעיונות דומים, אך הפולינום $\ f$ אינו עוד ריבועי, וכך הפירוק אינו נעשה במספרים שלמים, אלא באיברים של חוג שלמים גדול יותר.

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

תיאור אלגוריתם נפת שדה המספרים כאמור מורכב מאוד, בקצרה הרעיון הבסיסי של פולרד היה למצוא פולינום מתוקן $\ f(x)$ מעל השלמים $\ x$ שהוא אי-פריק ובעל מעלה $\ d$ נמוכה ולמצוא שלם $\ m$ המקיים $\ f(m)\equiv 0\ ({\mbox{mod }}n)$ למשל עבור מספר פרמה התשיעי $\ n=2^{2^{9}}+1$ זה קל כיוון ש-$\ 8n=2^{515}+8$ לכן אם $\ f(x)=x^{5}+8$ אז $\ m=2^{103}$. אולם עבור שלמים פריקים אחרים זה קצת יותר מורכב, הטריק הוא לקבוע תחילה את המעלה (אותה מחשבים על ידי $\ d\approx \left({\frac {3\ln n}{2\ln \ln n}}\right)$ בדרך כלל $\ d$ הוא שלם אי זוגי קטן כגון $\ d=5$).

לאחר מכן קובעים את $\ m=\lfloor n^{1/d}\rfloor$ (או $\ m=\lfloor {\sqrt[{d}]{n}}\rfloor$) ומייצגים את $\ n$ בבסיס $\ m$ כך ש-

$\ n=c_{d}m^{d}+c_{d-1}m^{d-1}+...+c_{1}m+c_{0}$ (המקדם $\ c_{d}$ הוא 1 אם $\ n>(2d)^{d}$).

כאשר המקדמים של $\ m$ מקיימים $\ 0\leq c_{i}<m$.

כעת ניתן להגדיר את הפולינום $\ f$:

$\ f(x)=c_{d}x^{d}+c_{d-1}x^{d-1}+...+c_{1}x+c_{0}$

כך שמתקיים $\ f(m)\equiv 0\ ({\mbox{mod }}n)$. בסבירות גבוהה $\ f(x)$ הוא אי-פריק (במקרה שלא הרי שעובדה זו יכולה לסייע במציאת הגורמים הראשוניים של $\ n$ בזמן פולינומי, מה שלא סביר שיקרה).

נסמן ב- $\ \alpha$ שורש כלשהו של $\ f(x)$ בשדה המספרים המרוכבים, ונתבונן בחוג $\ \mathbb {Z} [\alpha ]$ הנוצר על ידי סיפוח השורש למספרים השלמים. היות ש-$\ f(m)\equiv 0\ ({\mbox{mod }}n)$ אפשר להחליף את כל המופעים של $\ \alpha$ בשארית $\ m{\mbox{ mod }}n$ ונקבל מיפוי טבעי $\ \phi$ מהחוג $\ \mathbb {Z} [\alpha ]$ ל-$\ \mathbb {Z} _{n}$ בתנאים האמורים $\ \phi$ הוא הומומורפיזם של חוגים.

אוספים קבוצה $\ S$ של זוגות זרים $\ a,b$ עם המאפיינים שכפולה של השלמים האלגבריים $\ a-\alpha b$ עבור כל הזוגות $\ a,b$ ב-$\ S$ הם מספר ריבועי ב-$\ \mathbb {Z} [\alpha ]$ נסמנו $\ \gamma ^{2}$, וכן כפולה של כל השלמים $\ a-mb$ עבור $\ a,b\in S$ היא מספר ריבועי ב-$\ \mathbb {Z}$ אותה נסמן $\ v^{2}$. אפשר להחליף את כל המופעים של $\ \alpha$ בשלם $\ m$ ומקבלים את $\ u$ כך שמתקיים $\ \phi (\gamma )\equiv u\ ({\mbox{mod }}n)$. ומזה נובע ש:

$\ u^{2}\equiv \phi (\gamma )^{2}=\phi (\gamma ^{2})=\phi \left(\prod _{a,b\in S}(a-\alpha b)\right)=\prod _{a,b\in S}\phi (a-\alpha b)\equiv \prod _{a,b\in S}(a-mb)\equiv v^{2}\ ({\mbox{mod }}n)$

וכעת יש לנו $\ u,v$ להם אנו זקוקים כדי לפרק את $\ n$ כיוון שכאמור אם $\ u\not \equiv \pm v\ ({\mbox{mod }}n)$ אז $\ {\mbox{gcd}}(u-v,n)$ הוא גורם לא טריוויאלי של $\ n$.

נותר לברר כיצד למצוא קבוצה $\ S$ כזו שמקיימת את שני המאפיינים המתוארים. לשם כך יש צורך למצוא מספרים חלקים, הטריק הוא להיעזר בנורמה. הנורמה של $\ a-\alpha b$ המסומנת $\ N(a-\alpha b)$ מעל $\ \mathbb {Q}$ קלה לחישוב והיא $\ b^{d}f(a/b)$. בהנחה ש-$\ a-\alpha b$ הוא מספר חלק אם הנורמה שלו חלקה. מוודים שהנורמה של המספרים האלגבריים חלקה, בשיטת הניפוי באמצעות וקטור המעריכים ואלגברה לינארית מעל השדה $\ \mathbb {F} _{2}$. כדי להבטיח כי גם כפולה של המספרים $\ a-\alpha b$ מעל $\ \mathbb {Z} [\alpha ]$ היא מספר חלק, נעזרים ברעיון חוג השלמים האלגברים $\ \mathbb {Q} (\alpha )$, עם התכונה שכל האידאליים הראשוניים הגורמים של $\ a-\alpha b$ עבור $\ a,b$ זרים, הם ממעלה 1 והנורמה שלהם היא ראשוני רציונלי. לכן בוחרים קבוצה $\ R_{p}$ עבור כל $\ p$, הכוללת את כל הראשוניים המקיימים $\ f(x)\equiv 0\ ({\mbox{mod }}p)$. אם מתקבל זוג $\ a,b$ כאשר הנורמה $\ N(a-\alpha b)$ מתחלקת ב-$\ p$ אזי גם $\ a-\alpha b$ מתחלק באחד האידאליים הראשוניים ב-$\ R_{p}$ וקל לדעת איזה מהם כי $\ a/b$ יהיה שקול מודולו $\ p$ לאחד מהם.

כדי להבטיח שכפולה של כל $\ a-\alpha b$ בחוג $\mathbb {Z} [\alpha ]$ נותנת מספר ריבועי נעזרים ברעיון של לן אדלמן שנקרא מציין הריבועי (quadratic character), לפי לז'נדר, למספר ריבועי מציין ריבועי 1 ביחס לכל הראשוניים שאינם מחלקים שלו. מגדירים קבוצה $\ Q$ הכוללת את כל השלמים שאינם מחלקים של $\ a-\alpha b$, משתמשים באלגברה לינארית כדי למצוא מספרים חלקים עם שני מאפיינים, האחד שוקטור המעריכים שלהם זוגי והשני שהמציין הריבועי שלהם הוא 1. בסיכויים גבוהים $\ a-\alpha b$ הוא מספר ריבועי.

כדי למצוא את $\ X$ ואת $\ Y$ המקיימים $\ X^{2}\equiv Y^{2}$ הדרושים לפירוק $\ n$, נותר לחשב את השורש הריבועי של הכפולה של כל $\ a-\alpha b$, כלומר השורש הריבועי $\ \beta ^{2}=\prod _{i}(a_{i}-\alpha b_{i})$, אותו קל יותר לחשב אותו כ-$\ \phi (\beta ^{2})=X^{2}$ ב-$\mathbb {Z} _{n}$, היות שמדובר בחישוב שורש בשדה $\ F_{p^{d}}$ אפשר להיעזר באלגוריתם יעיל לחישוב שורשים ריבועיים בשדות ראשוניים, כמו אלגוריתם Shanks-Tonelli או אלגוריתם מונטגומרי ואז לפתור את מערכת השקילויות באמצעות משפט השאריות הסיני כדי לקבל את $\ X$. ולסיום נותר לחשב את המחלק המשותף המרבי של $\ (x-y,n)$ ומתקבל גורם ראשוני של $\ n$.

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

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

קישורים חיצוניים

• המאמר A Tale of Two Sieves של קרל פומרנץ ממציא הנפה הריבועית ונמנה עם מפתחי NFS.
• מאמר על פולינומים ממעלה שנייה לנפת שדה המספרים של Brian Murphy ו-Richard Brent.
• Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag