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

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

סיבוכיות

עם הופעתן של מערכת ההצפנה הא-סימטרית RSA, המבוססת על הקושי שבפירוק מספרים גדולים לגורמים, עלה קרנה של בעיה זו בתורת המספרים היישומית. בבעיית פירוק מספר נתון , גודל הקלט מורכב ממספר הספרות הבינאריות ומסומן . סיבוכיות פולינומית היא מהצורה  עבור קבוע  כלשהו גדול מ-0. לעומת זאת סיבוכיות אקספוננציאלית היא מהצורה ; אלגוריתם בעל סיבוכיות כזו נחשב בדרך כלל לגרוע במיוחד. לא ידוע כיום על אלגוריתם בעל סיבוכיות פולינומית לבעיית הפירוק והעוסקים בתחום מעריכים שאלגוריתם כזה כלל אינו קיים. למעשה, עד להמצאתה של הנפה הריבועית, כל האלגוריתמים לבעיית הפירוק היו אקספוננציאליים.
סיבוכיות פירוק  לגורמים באמצעות שיטת הנפה הריבועית מוערכת ב-, כאשר 
היא פונקציית הסיבוכיות המתאימה לאלגוריתמים מסוג זה.  הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל- הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של , הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש- גדול יותר. לשם השוואה,  היא סיבוכיות אקספוננציאלית, בעוד ש- היא סיבוכיות פולינומית. על סולם זה, הסיבוכיות של הנפה הריבועית נמצאת ב"אמצע הדרך" בין סיבוכיות אקספוננציאלית לפולינומית, והיא כאמור הראשונה שפרצה את מחסום האקספוננציאליות. משך זמן רב עמדה בעיית הפירוק על סיבוכיות של  והושגו רק שיפורים מינוריים בערכו של הקבוע . 
פריצת הדרך ארעה ב-1988, כאשר המתמטיקאים ג'ון פולארד, מארק מאנאס, הנדריק לנסטרה וארג'ן לנסטרה פרסמו את שיטת "נפת שדה המספרים המיוחדת", שנועדה לפירוק מספרים בעלי מבנה מיוחד, כזה של מספרי פרמה ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה  כשהקבוע . כמספר שנים לאחר מכן, פותח האלגוריתם הכללי - "נפת שדה המספרים הכללית", המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-, כשהקבוע . בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות - אך אינן מוכחות.

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

הרעיון של נפת שדה המספרים החל עם עבודתם של דון קופרסמיט, אנדרו אודליצקו וריצ'רד שרופל, שניסו באמצע שנות התשעים לפתור את בעיית לוגריתם דיסקרטי באמצעות אלגוריתם שדה המספרים הריבועיים (Quadratic Number Field). הרעיון צד את עינו של פולרד שהציע ב-1988 לנצל את האלגוריתם גם לפירוק לגורמים של מספרים מהצורה  כאשר  קטן בשיטה שכונתה שדה מספרים אלגבריים. תחילה נוסה האלגוריתם בהצלחה בפירוק המספר  כאשר . מאוחר יותר הרחיבו האחים לנסטרה, מאנאס ופולרד עצמו את האלגוריתם לפירוק מספרים מהצורה  כאשר  הוא שלם חיובי קטן ו- קטן. מספרים אילו נקראים מספרי קנינגהם (Cunningham), האלגוריתם כונה נפת שדה מספרים מיוחדת (SNFS), יישום זה של האלגוריתם שימש בפירוק מספר פרמה התשיעי  (בסדר גודל של 155 ספרות עשרוניות), שהתגלה ככפולה של שלושה מספרים ראשוניים. 
הגרסה הכללית של האלגוריתם פותחה ושופצה על ידי מתמטיקאים רבים בראשם ג'ו בוהלר, ארג'ן לנסטרה, קרל פומרנץ דון קופרסמיט ורבים אחרים. קופרסמיט הציע שיפורים אחדים שייעלו את האלגוריתם לזמן של  ומקום בסדר גודל . מאוחר יותר דווח צוות מתמטיקאים בראשות ברנשטיין ולנסטרה שהפעילו את האלגוריתם באופן מקבילי עם 16,384 מעבדים ופרקו בהצלחה מספר בגודל 119 ספרות עשרוניות בזמן קצר יחסית. קצב השיפור רק עלה במרוצת השנים. לנסטרה הכריז על הצלחתו לפרק באמצעות האלגוריתם, מודולוס RSA (ממספרי האתגר של מעבדות RSA), בגודל 130 ספרות עשרוניות. בנובמבר 2005 שימש האלגוריתם בהצלחה לפירוק המודולוס RSA-200 (בגודל 200 ספרות עשרוניות) גם הוא ממספרי האתגר. זהו המספר הגדול ביותר שפורק לגורמים נכון להיום. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל.
הסיבה העיקרית לכך שזמן הריצה של אלגוריתם נפת שדה המספרים קטן בהשוואה לנפה הריבועית נעוצה במספרים החלקים הקטנים יחסית הדרושים לו לעומת הנפה הריבועית. מידת הצלחת האלגוריתם תלויה באיסוף כמות נכבדה של מספרים חלקים, אולם אילו אינם מצויים בשפע וככל שהמספרים גדולים יותר כך פוחתים הסיכויים שיהיו חלקים. וככל שהמספרים החלקים קטנים יותר האלגוריתם יעיל יותר.

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

מספרי פרמה  קרויים על שמו של פייר דה פרמה, שהתעניין בפירוק לגורמים בשל הקשר למספרים משוכללים ומספרים ידידים. הוא טען כי מספרים מהצורה  יכולים להיות ראשוניים רק אם  הוא חזקה של . הוא האמין שמספרים אילו ראשוניים כולם. כיום ידוע שלא, למשל  אינו ראשוני, אם כי פרמה עצמו החמיץ עובדה זו מסיבה לא ידועה. שנים לאחר מכן הוכיח גאוס את חשיבות מספרי פרמה בגאומטריה אלמנטרית ומתמטיקאים רבים ניסו כוחם בפירוק מספרי פרמה תוך שימוש במיטב האלגוריתמים הידועים בתקופתם. 
הבעיה הורחבה לבעיה כללית יותר של פירוק מספרים מהצורה  (כאשר  קטן ו- גדול), מספרים אילו מכונים מספרי קנינגהם על שם המתמטיקאי אלן ג'וזף קנינגהם (Allan J. C. Cunningham). פרויקט קנינגהם הווה כעין מבחן כח להתקדמות בתחום הכללי של פירוק לגורמים. ב-1880 מצאו מתמטיקאים את הגורמים הראשוניים של , רק כמאה שנים לאחר מכן ב-1970 הצליחו מוריסון וברילהרט לפרק את  באמצעות שברים משולבים. מספר פרמה השמיני פורק ב-1980 על ידי ברנט ופולרד באמצעות גרסה של אלגוריתם rho של פולרד היעיל במיוחד במציאת גורמים קטנים. מספר פרמה התשיעי פורק לחלוטין ב-1990 על ידי האחים לנסטרה, מאנאס ופולרד שעשו זאת במאמץ שנמשך כארבעה חודשים, באמצעות נפת שדה המספרים והשתמשו בכח חישוב של כשבע מאות מחשבים שגויסו ממקומות שונים ברחבי העולם ומחשב-על אחד שריכז את העבודה. מספר פרמה העשירי פורק לגורמים ב-1999 על ידי ריצ'רד ברנט באמצעות שיטת העקום האליפטי . ב-1988 נעשה שימוש באותה שיטה כדי לפרק לגורמים את  (שגורמיו הראשוניים נמצאו כולם קטנים). גורמים ראשוניים אחדים של מספרי פרמה מסוימים עד  נמצאו גם הם, אך פירוקם המלא של מספרים אילו לגורמים טרם צלח.
מכל השיטות האחרות שחלקן הוזכרו, נפת שדה המספרים נחשבת לשיטה היעילה ביותר לפירוק מספרי פרמה ומספרי קנינגהם. אולם חשיבותם של מספרים אילו כמדד יעילות בפירוק לגורמים הולכת ודועכת לאחרונה, מהסיבה הפשוטה שהמספרים שיש בהם עניין מיוחד כיום (המשמשים בדרך כלל במערכות הצפנה) קשים בהרבה לפירוק ממספרי פרמה המקבילים להם. למשל מודלוס בגודל 512 סיביות (שהוא כפולה של שני מספרים ראשוניים גדולים), דורש זמן ומשאבים פיננסיים הגדולים במידה נכרת מהזמן והמשאבים שנדרשו בפירוק מספר פרמה התשיעי.