הבעיה הורחבה לבעיה כללית יותר של פירוק מספרים מהצורה formula_10 (כאשר formula_11 קטן ו-formula_7 גדול), מספרים אילו מכונים מספרי קנינגהם על שם המתמטיקאי אלן ג'וזף קנינגהם (Allan J. C. Cunningham). פרויקט קנינגהם היווה מעין מבחן כוח להתקדמות בתחום הכללי של פירוק לגורמים. ב-1880 מצאו מתמטיקאים את הגורמים הראשוניים של formula_13, רק כמאה שנים לאחר מכן ב-1970 הצליחו מוריסון וברילהרט לפרק את formula_14 באמצעות שברים משולבים. מספר פרמה השמיני פורק ב-1980 על ידי ברנט ופולרד באמצעות גרסה של אלגוריתם rho של פולרד היעיל במיוחד במציאת גורמים קטנים. מספר פרמה התשיעי פורק לחלוטין ב-1990 על ידי האחים לנסטרה, מאנאס ופולרד שעשו זאת במאמץ שנמשך כארבעה חודשים, באמצעות נפת שדה המספרים והשתמשו בכוח חישוב של כשבע מאות מחשבים שגויסו ממקומות שונים ברחבי העולם ומחשב-על אחד שריכז את העבודה. מספר פרמה העשירי פורק לגורמים ב-1999 על ידי ריצ'רד ברנט באמצעות שיטת העקום האליפטי. ב-1988 נעשה שימוש באותה שיטה כדי לפרק לגורמים את formula_15 (שגורמיו הראשוניים (פרט לגדול ביותר) נמצאו כולם קטנים). עד היום (2010), נמצאו כ-250 גורמים ראשוניים של מספרי פרמה מ-formula_16 עד formula_17, כאשר מספר פרמה הקטן ביותר שעדיין לא ידוע האם הוא פריק או ראשוני הוא formula_18. אך פירוקם המלא של מספרים אלו לגורמים טרם צלח.
חשיבותם של מספרי קנינגהם כמדד יעילות בפירוק לגורמים הולכת ודועכת לאחרונה, מהסיבה הפשוטה שהמספרים שיש בהם עניין מיוחד כיום (המשמשים בדרך כלל במערכות הצפנה) קשים בהרבה לפירוק ממספרי פרמה המקבילים להם. למשל מודלוס בגודל 512 סיביות (שהוא כפולה של שני מספרים ראשוניים גדולים), דורש זמן ומשאבים פיננסיים הגדולים במידה ניכרת מהזמן והמשאבים שנדרשו בפירוק מספר פרמה התשיעי (המקביל לו).
יעילות אלגוריתמים שונים לפירוק לגורמים.
לבעיית הפירוק לגורמים לא ידוע פתרון יעיל אלגוריתמית, כלומר כזה שזמן ריצתו פולינומי ביחס למספר הספרות במספר שמפרקים. ההשערה הרווחת היא שפתרון כזה לא קיים (משמע בעיית הפירוק לגורמים אינה ב-P) ועל השערה זו מבוססות שיטות הצפנה רבות כגון RSA. עם זאת, מבין הבעיות שאינן ניתנות לפתרון יעיל, בעיית הפירוק לגורמים נחשבת ל"קלה באופן יחסי". בפרט סבורים שהיא אינה בעיה NP-קשה. עדות לסברה זו היא אלגוריתם שור, אלגוריתם קוונטי שפותר את בעיית הפירוק לגורמים בזמן פולינומי (מכאן שאילו בעיית הפירוק לגורמים הייתה NP-קשה, אזי NP הייתה מוכלת ב-BQP בניגוד להשערה הרווחת). כמו כן ידוע שבעיית הפירוק לגורמים שייכת ל-co-NP, ולכן אילו היא הייתה NP-קשה הדבר היה גורר NP=co-NP, תוצאה הנחשבת מאוד לא סבירה.
מבין כל האלגוריתמים הידועים לפירוק לגורמים עד 1988, נחשב אלגוריתם הנפה הריבועית כאלגוריתם היעיל ביותר לפירוק מספרים גדולים, טוב יותר מפירוק לגורמים באמצעות עקום אליפטי (שיטה שהציע קרל פומרנץ ב-1984) ומאלגוריתם הנפה הרציונלית של דיקסון, אולם עם פרסומו של אלגוריתם נפת שדה מספרים על ידי פולרד, התגלה האחרון כאלגוריתם הטוב ביותר בכל הזמנים לפירוק לגורמים. בשיטה זו פורק המספר RSA-130 בקרוב ל-15 אחוז מהזמן שלקח לנפה הריבועית. נכון לשנת 2007, נפת שדה המספרים נחשבת לשיטה היעילה ביותר הידועה כיום לפירוק מספרים גדולים מאוד לגורמים ונמצאת בעיצומו של תהליך מחקר ופיתוח.
הפרש מספרים ריבועיים.
רעיון הפרש המספרים הריבועיים, מבואר היטב במאמרו של קרל פומרנץ "A Tale of Two Sieves". הוא סיפר שבתחרות מתמטית שבה השתתף כסטודנט ב-1960 הוצג התרגיל: פירוק המספר 8051 לגורמים ראשוניים בתוך חמש דקות (באותה שנה מחשבונים טרם הומצאו). לא קשה לבצע חילוק ניסיוני עד שורש המספר (בערך 90) בתוך חמש דקות, אולם כבכל תחרות הרעיון היה למצוא את הטריק שיקצר את הדרך משמעותית. התשובה פשוטה; ניתן להציג את המספר formula_19 גם כהפרש formula_20, ולכן formula_21. על טריק זה המכונה הפרש ריבועים, מבוססת שיטת הפירוק לגורמים של המתמטיקאי הצרפתי פרמה. קל להבין זאת אם זוכרים שכל מספר פריק אי-זוגי ניתן לייצוג כהפרש הריבועים:
כמו שבחילוק ניסיוני (Trial Division) ישנם מקרים קלים כגון אם המספר מכיל גורמים קטנים כלשהם, כך גם בשיטת פרמה. התרגיל המתואר הוא מקרה קל של שיטת פרמה היעילה בתנאי שגורמי המספר אותו מעוניינים לפרק קרובים מאוד לשורשים ריבועיים. אולם במקרה הגרוע שיטת פרמה יעילה פחות מחילוק ניסיוני. מרבית המספרים נופלים בקטגוריה השנייה, כלומר במקרה הממוצע שיטת פרמה אינה יעילה.
קרייצ'יק העלה רעיון לשיפור שיטת פרמה, מה שהפך לאחר מכן כבסיס למרבית האלגוריתמים המודרניים. במקום למצוא שלמים formula_23 המקיימים formula_24 עבור השלם formula_25 אותו אנו מעוניינים לפרק, מספיק למצוא שלמים כאלו שהם כפולה של formula_25 כלומר formula_27. לשקילות האחרונה יכולים להיות שני פתרונות, האחד 'אינו מעניין' כאשר formula_28 ושני 'מעניין' כאשר formula_29. האחרון מעניין כיוון שלפחות למחצית השלמים הזרים ל-formula_25 קיים פתרון כזה אם formula_25 אי זוגי ומתחלק לכל הפחות בשני ראשוניים שונים. וזה מעניין משום שהמחלק המשותף המרבי של formula_25 ו-formula_33 הוא גורם ראשוני של formula_25. זאת משום ש-formula_25 הוא מחלק של formula_36, אולם אינו מחלק אף גורם מהם (כלומר את formula_37 או את formula_38 עצמם), עובדה זו מעידה על כך ש-formula_25 נמצא היכן שהוא בין formula_33 ל-formula_41.
לדוגמה אם formula_42, המספר הריבועי הסמוך ל-formula_25 מעליו הוא formula_44. אם נגדיר פולינום ממעלה שנייה formula_45 עבור השלמים formula_46 נקבל את התוצאות formula_47. אמנם עדיין לא נמצא מספר ריבועי כלשהו אולם הרעיון הוא למצוא מספר שלמים formula_48 כאלו המקיימים:
הפתרון ל-formula_27 כעת ברור. אולם כיצד למצוא formula_48ים כאלו שכפולת הפולינומים מעליהם נותנת מספר ריבועי? הרעיון של קרייצ'יק הוא שחלק מהפולינומים formula_54 ניתנים לפירוק לגורמים יחסית בקלות, כפי שרואים: formula_55 וכן formula_56. מתוך הפירוק של ארבעה מספרים אילו אפשר לראות ש-formula_57 הוא מספר ריבועי וכך מצאנו את formula_27 כאשר:
הרעיון כמעט הושלם, היות ש-formula_61, אפשר להשתמש באלגוריתם אוקלידס לחישוב מחלק משותף מקסימלי של formula_62 ומצאנו ש-formula_63. איך ידענו למצוא את ה-formula_48ים הנכונים? הרעיון של קרייצ'יק היה פשוט לחפש אותם סדרתית. אלגוריתם קרייצ'יק פותח לאחר מכן על ידי מספר מתמטיקאים, הצעה אחת הייתה להחליף את הפונקציה formula_45 בפונקציה עדיפה הנובעת מהרחבה של השברים המשולבים של שורש formula_25. מסתבר שחיפוש יעיל של סדרה כזו של formula_48ים המקיימת את התנאי האמור היא בעצם המשימה העיקרית בכל אלגוריתם לפירוק לגורמים.
אלגוריתמים מתקדמים.
קרל פומרנץ ניצל את האסטרטגיה של ברילהרט ומוריסון כדי לפתח על בסיס שיטת קרייצ'יק את אלגוריתם הנפה הריבועית. הדרך למצוא סדרה המניבה מספר ריבועי נעשית באמצעות אלגברה ליניארית. אם מתייחסים לוקטור formula_68 כוקטור של מעריכים של הגורמים של formula_7, אזי אפשר לראות שרק אם סכום המעריכים זוגי יתקבל מספר ריבועי. לכן התכסיס הוא לחפש מספרים שניתן לייצגם ככפולה של סדרה קטנה של חזקות ראשוניים אותה מכנים 'בסיס גורמים'. אפשר ל'שחק' בכמה מספרים כאלו עד שעולים על תלות ליניארית של וקטור המעריכים (כלומר וקטור שסכומו אפס) ומשם הדרך למציאת מספר ריבועי מתאים קלה. במרוצת הזמן נוספו עוד שיפורים לאלגוריתם הנפה הריבועית על ידי מתמטיקאים רבים.
הדרך לפיתוח אלגוריתם נפת שדה המספרים עוברת דרך הרעיונות המתוארים, אם כי אלגוריתם נפת שדה המספרים הרבה יותר מורכב מקודמיו. במהותו האלגוריתם מבוסס על שיטת פרמה, המציגה את המספר כהפרש של מספרים ריבועיים. אולם הדרך להשיג זאת שונה בתכלית. הגרסה הראשונה שהעלה פולרד התאימה במיוחד למספרים בעלי מבנה מיוחד כמספרי פרמה. האלגוריתם נקרא SNFS קיצור של Special number filed sieve והוא היעיל ביותר הידוע עבור מספרים אילו. מאוחר יותר הורחב האלגוריתם לפירוק כל סוג של מספר. נפת שדה המספרים משתמשת בכמה רעיונות מתקדמים בתורת המספרים כמו שדות אלגבריים מעל מספרים רציונליים, הומומורפיזם, ראשוניים אידיאליים ונורמה של מרחבים וקטוריים מעל שדות מרוכבים. גם לאלגוריתם זה נוספו שיפורים לא מעטים במשך הזמן, על ידי מתמטיקאים רבים ביניהם קופרסמיט, ויידמן, בוהלר, פומרנץ, אודליצקו ואחרים.
אלגוריתמים קוונטיים.
בהנחה שמחשבים קוונטיים בקנה מידה מלא יהיו מעשיים בזמן הקרוב ניתן יהיה לפרק כל מספר גדול לגורמים בסיבוכיות זמן של formula_70 באמצעות אלגוריתם שור. לעובדה זו השלכות מרחיקות לכת על תורת ההצפנה וכבר בימינו שוקדים מדענים על פיתוח אלגוריתמים פוסט-קוונטיים שיעמדו בפני קריפטואנליזה על מחשב קוונטי כאשר יהיה מעשי. ההערכות מדברות על פחות מ-15 שנה. נכון לשנת 2015 המחשב הקוונטי הגדול ביותר הוא בקנה מידה של 1000 קיוביטים. מהיבט של קריפטוגרפיה זה די נמוך מהגודל הדרוש כדי לפרק לגורמים מספרים בהם משתמשים במערכות הצפנה מודרניות.
סתיו
הסתיו הוא אחת מארבע עונות השנה, מציין את המעבר בין הקיץ לחורף ולכן מכונה עונת מעבר.