היא פונקציית הסיבוכיות המתאימה לאלגוריתמים מסוג זה. formula_9 הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל-formula_9 הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של formula_9, הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש-formula_4 גדול יותר. לשם השוואה, formula_13 היא סיבוכיות אקספוננציאלית, בעוד ש-formula_14 היא סיבוכיות פולינומית. על סולם זה, הסיבוכיות של הנפה הריבועית נמצאת ב"אמצע הדרך" בין סיבוכיות אקספוננציאלית לפולינומית, והיא כאמור הראשונה שפרצה את מחסום האקספוננציאליות. משך זמן רב עמדה בעיית הפירוק על סיבוכיות של formula_7 והושגו רק שיפורים מינוריים בערכו של הקבוע formula_4.
פריצת הדרך ארעה ב-1988, כאשר המתמטיקאים ג'ון פולארד, מארק מאנאס, הנדריק לנסטרה וארג'ן לנסטרה פרסמו את שיטת "נפת שדה המספרים המיוחדת", שנועדה לפירוק מספרים בעלי מבנה מיוחד, כזה של מספרי פרמה ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה formula_17 כשהקבוע formula_18. כמספר שנים לאחר מכן, פותח האלגוריתם הכללי - "נפת שדה המספרים הכללית", המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-formula_17, כשהקבוע formula_20. בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות - אך אינן מוכחות.
לידתה של נפת שדה המספרים.
הרעיון של נפת שדה המספרים החל עם עבודתם של דון קופרסמיט, אנדרו אודליצקו וריצ'רד שרופל, שניסו באמצע שנות התשעים לפתור את בעיית לוגריתם דיסקרטי באמצעות אלגוריתם שדה המספרים הריבועיים (Quadratic Number Field). הרעיון צד את עינו של פולרד שהציע ב-1988 לנצל את האלגוריתם גם לפירוק לגורמים של מספרים מהצורה formula_21 כאשר formula_22 קטן בשיטה שכונתה שדה מספרים אלגבריים. תחילה נוסה האלגוריתם בהצלחה בפירוק המספר formula_23 כאשר formula_24. מאוחר יותר הרחיבו האחים לנסטרה, מאנאס ופולרד עצמו את האלגוריתם לפירוק מספרים מהצורה formula_25 כאשר formula_26 הוא שלם חיובי קטן ו-formula_27 קטן. מספרים אילו נקראים מספרי קנינגהם (Cunningham), האלגוריתם כונה נפת שדה מספרים מיוחדת (SNFS), יישום זה של האלגוריתם שימש בפירוק מספר פרמה התשיעי formula_28 (בסדר גודל של 155 ספרות עשרוניות), שהתגלה ככפולה של שלושה מספרים ראשוניים.
הגרסה הכללית של האלגוריתם פותחה ושופצה על ידי מתמטיקאים רבים בראשם ג'ו בוהלר, ארג'ן לנסטרה, קרל פומרנץ דון קופרסמיט ורבים אחרים. קופרסמיט הציע שיפורים אחדים שייעלו את האלגוריתם לזמן של formula_29 ומקום בסדר גודל formula_30. מאוחר יותר דווח צוות מתמטיקאים בראשות ברנשטיין ולנסטרה שהפעילו את האלגוריתם באופן מקבילי עם 16,384 מעבדים ופרקו בהצלחה מספר בגודל 119 ספרות עשרוניות בזמן קצר יחסית. קצב השיפור רק עלה במרוצת השנים. לנסטרה הכריז על הצלחתו לפרק באמצעות האלגוריתם, מודולוס RSA (ממספרי האתגר של מעבדות RSA), בגודל 130 ספרות עשרוניות. בנובמבר 2005 שימש האלגוריתם בהצלחה לפירוק המודולוס RSA-200 (בגודל 200 ספרות עשרוניות) גם הוא ממספרי האתגר. זהו המספר הגדול ביותר שפורק לגורמים נכון להיום. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל.
הסיבה העיקרית לכך שזמן הריצה של אלגוריתם נפת שדה המספרים קטן בהשוואה לנפה הריבועית נעוצה במספרים החלקים (ראה להלן הסבר) הקטנים יחסית הדרושים לו לעומת הנפה הריבועית. מידת הצלחת האלגוריתם תלויה באיסוף כמות נכבדה של מספרים חלקים, אולם אילו אינם מצויים בשפע וככל שהמספרים גדולים יותר כך פוחתים הסיכויים שיהיו חלקים. וככל שהמספרים החלקים קטנים יותר האלגוריתם יעיל יותר.
מספרי פרמה ומספרי קנינגהם.
מספרי פרמה formula_31 קרויים על שמו של פייר דה פרמה, שהתעניין בפירוק לגורמים בשל הקשר למספרים משוכללים ומספרים ידידים. הוא טען כי מספרים מהצורה formula_32 יכולים להיות ראשוניים רק אם formula_33 הוא חזקה של formula_34. הוא האמין שמספרים אילו ראשוניים כולם. כיום ידוע שלא, למשל formula_35 אינו ראשוני, אם כי פרמה עצמו החמיץ עובדה זו מסיבה לא ידועה. שנים לאחר מכן הוכיח גאוס את חשיבות מספרי פרמה בגאומטריה אלמנטרית ומתמטיקאים רבים ניסו כוחם בפירוק מספרי פרמה תוך שימוש במיטב האלגוריתמים הידועים בתקופתם.
הבעיה הורחבה לבעיה כללית יותר של פירוק מספרים מהצורה formula_36 (כאשר formula_37 קטן ו-formula_33 גדול), מספרים אילו מכונים מספרי קנינגהם על שם המתמטיקאי אלן ג'וזף קנינגהם (Allan J. C. Cunningham). פרויקט קנינגהם הווה כעין מבחן כח להתקדמות בתחום הכללי של פירוק לגורמים. ב-1880 מצאו מתמטיקאים את הגורמים הראשוניים של formula_39, רק כמאה שנים לאחר מכן ב-1970 הצליחו מוריסון וברילהרט לפרק את formula_40 באמצעות שברים משולבים. מספר פרמה השמיני פורק ב-1980 על ידי ברנט ופולרד באמצעות גרסה של אלגוריתם rho של פולרד היעיל במיוחד במציאת גורמים קטנים. מספר פרמה התשיעי פורק לחלוטין ב-1990 על ידי האחים לנסטרה, מאנאס ופולרד שעשו זאת במאמץ שנמשך כארבעה חודשים, באמצעות נפת שדה המספרים והשתמשו בכח חישוב של כשבע מאות מחשבים שגויסו ממקומות שונים ברחבי העולם ומחשב-על אחד שריכז את העבודה. מספר פרמה העשירי פורק לגורמים ב-1999 על ידי ריצ'רד ברנט באמצעות שיטת העקום האליפטי . ב-1988 נעשה שימוש באותה שיטה כדי לפרק לגורמים את formula_41 (שגורמיו הראשוניים נמצאו כולם קטנים). גורמים ראשוניים אחדים של מספרי פרמה מסוימים עד formula_42 נמצאו גם הם, אך פירוקם המלא של מספרים אילו לגורמים טרם צלח.
מכל השיטות האחרות שחלקן הוזכרו, נפת שדה המספרים נחשבת לשיטה היעילה ביותר לפירוק מספרי פרמה ומספרי קנינגהם. אולם חשיבותם של מספרים אילו כמדד יעילות בפירוק לגורמים הולכת ודועכת לאחרונה, מהסיבה הפשוטה שהמספרים שיש בהם עניין מיוחד כיום (המשמשים בדרך כלל במערכות הצפנה) קשים בהרבה לפירוק ממספרי פרמה המקבילים להם. למשל מודלוס בגודל 512 סיביות (שהוא כפולה של שני מספרים ראשוניים גדולים), דורש זמן ומשאבים פיננסיים הגדולים במידה נכרת מהזמן והמשאבים שנדרשו בפירוק מספר פרמה התשיעי.
שיטת הנפה הריבועית.
מלבד חלוקה נסיונית (Trial Division) הנאיבית, כל שיטות הפירוק הידועות כיום מבוססות על רעיון אחד: כדי לפרק את המספר formula_1, יש לאתר זוג ריבועים, השקולים זה לזה מודולו formula_1. אם formula_45 ו- formula_46, אז formula_47 הוא גורם לא טריוויאלי של formula_1
(gcd מסמן את המחלק המשותף המקסימלי).
אם formula_1 פריק והמספרים formula_50 ו-formula_51 (או לפחות אחד מהם) אקראיים וריבועיהם שקולים מודולו formula_1, הסיכוי לכך ש-formula_53 אינו עולה על חצי; לכן מספיק לאתר פתרונות למשוואה formula_54 האמורה, ובמקרה של כישלון לנסות לאתר זוג אחר. הדרך להשיג זוג כזה הוצעה לראשונה על ידי דיקסון ונוסתה לראשונה במסגרת שיטת הנפה הריבועית. היא מבוססת על כך שגם אם קשה לפרק את formula_1, ישנם מספרים שקל לפרקם, אלו שכל גורמיהם קטנים יחסית (וניתנים לניחוש). בוחרים "בסיס" המורכב מ-m הראשוניים הקטנים ביותר formula_56 ומספר שכל גורמיו נמצאים ב-formula_57 נקרא "F-חלק". כעת מחפשים באקראי מספרים formula_58, כך ש-formula_59 הוא מספר חלק ביחס ל-formula_57. מכיוון שהפירוק של כל אחד מהמספרים formula_61 ידוע, אפשר לחפש מכפלות של מספרים כאלה, השוות בעצמן לריבוע. חיפוש זה נעשה באמצעות דירוג של מטריצת המעריכים שהתקבלה מן הפירוקים השונים, מודולו 2, וחיפוש תלות ליניארית בין וקטורי המעריכים. אותה מכפלה formula_62 היא, מחד, מכפלה של גורמים ראשוניים שכל אחד מהם מופיע מספר זוגי של פעמים, ומאידך שקולה מודולו formula_1 לריבוע של formula_64. כך מתקבל זוג הריבועים המבוקש.
אלגוריתם נפת שדה המספרים משתמש ברעיונות דומים, אך הפולינום formula_65 אינו עוד ריבועי, וכך הפירוק אינו נעשה במספרים שלמים, אלא באיברים של חוג שלמים גדול יותר.
תקציר האלגוריתם.
תיאור אלגוריתם נפת שדה המספרים כאמור מורכב מאוד, בקצרה הרעיון הבסיסי של פולרד היה למצוא פולינום מתוקן formula_66 מעל השלמים formula_50 שהוא אי-פריק ובעל מעלה formula_68 נמוכה ולמצוא שלם formula_33 המקיים formula_70 למשל עבור מספר פרמה התשיעי formula_71 זה קל כיוון ש-formula_72 לכן אם formula_73 אז formula_74. אולם עבור שלמים פריקים אחרים זה קצת יותר מורכב, הטריק הוא לקבוע תחילה את המעלה (אותה מחשבים על ידי formula_75 בדרך כלל formula_68 הוא שלם אי זוגי קטן כגון formula_77).
לאחר מכן קובעים את formula_78 (או formula_79) ומייצגים את formula_1 בבסיס formula_33 כך ש-
כעת ניתן להגדיר את הפולינום formula_65:
כך שמתקיים formula_89. בסבירות גבוהה formula_66 הוא אי-פריק (במקרה שלא הרי שעובדה זו יכולה לסייע במציאת הגורמים הראשוניים של formula_1 בזמן פולינומי, מה שלא סביר שיקרה).
נסמן ב- formula_9 שורש כלשהו של formula_66 בשדה המספרים המרוכבים, ונתבונן בחוג formula_94 הנוצר על ידי סיפוח השורש למספרים השלמים. היות ש-formula_70 אפשר להחליף את כל המופעים של formula_9 בשארית formula_97 ונקבל מיפוי טבעי formula_98 מהחוג formula_94 ל-formula_100 בתנאים האמורים formula_98 הוא הומומורפיזם של חוגים.