פירוק לגורמים של מספר שלם

במתמטיקה, פירוק לגורמים של מספר שלם הוא פירוקו של המספר למספרים קטנים יותר, הקרויים גורמים, כך שמכפלת הגורמים זה בזה תתן את המספר המקורי. לדוגמה, את המספר 6936 ניתן לפרק לגורמים ראשוניים 17² · 3 · 2³ = 6936.
לפי המשפט היסודי של האריתמטיקה, לכל מספר טבעי גדול מ-1 קיימת הצגה יחידה כמכפלה של מספרים ראשוניים (עד כדי שינוי סדר הופעת הגורמים). תכונה זו של המספרים הראשוניים הופכת אותם למעין "אטומים" של המספרים השלמים.
ידיעת הפירוק לגורמים ראשוניים של מספר מסוים מספקת ידיעה מלאה על כל מחלקיו של מספר זה. דוגמה: הפירוק לגורמים של המספר 6936 המופיע לעיל מלמד אותנו שכל מחלק של מספר זה הוא מהצורה  כאשר 
. 
זה מביא אותנו ל-3 · 2 · 2 · 2 = 24 מחלקים בסך הכל.
פירוק לגורמים של מספר שלם גדול במיוחד (בן מאות ספרות) הוא בעיה שפתרונה, באמצעות האלגוריתמים הידועים כעת למטרה זו, דורש מאות שנים, גם כאשר משמשים למטרה זו המחשבים המהירים ביותר. קושי זה הוא הבסיס לשיטות הצפנה א-סימטרית רבות.

פירוק מספר גדול לגורמים

עד אמצע המאה ה-20 הבעיה העסיקה מעטים שהתמידו בחיפוש שיטות יעילות יותר לפירוק מספרים גדולים לגורמים. בחצי השני של המאה העשרים, עם התפתחות המחשבים ועלייתה של הקריפטוגרפיה, במיוחד מערכות אבטחה אסימטריות שמסתמכות על פירוק לגורמים ככלי הצפנה כמו RSA ודומיה, עלתה רמת העניין בבעיה זו. כיום הבעיה נחשבת לאחת הבעיות החשובות בתורת המספרים והיא מעסיקה מתמטיקאים רבים מכל העולם. חשיבותה נודעת לא רק מהיבט קריפטוגרפי אלא בעיקר כבעיה חישובית המשמשת כמדד יכולת וידע טכנולוגי. חברת RSA פירסמה בעבר רשימת מספרים שהם כפולה של שני ראשוניים גדולים, שהציבה כאתגר לציבור עם פרס בצידם למי שיצליח לפרקם לגורמים. מספרים אילו מכונים מספרי האתגר של RSA ומיוצגים על ידי RSA-xxxx כשה-xים מציינים את מספר הספרות (בבסיס בינארי, ולעיתים בבסיס עשר). למשל הפרס למי שיצליח לפרק לגורמים את המספר RSA-2048 (בגודל 617 ספרות עשרוניות) היה 200,000 דולר. אולם פרויקט האתגר בוטל בראשית 2008.
לפני שלוש מאות שנה, שיער המתמטיקאי הצרפתי מרן מרסן שהמספר  פריק. 100 שנים מאוחר יותר הוכח שהוא צדק, עם זאת אפילו רק לפני כשני עשורים, המאמץ שנדרש לפירוק מספר זה היה כמעט מעבר ליכולת הטכנולוגית באותה עת. ב-1984 ההערכה הייתה שלפירוק המספר יידרשו  שנים בקירוב. המספר פורק בהצלחה באותה שנה בתוך 32 שעות, שיא עולמי. אם בשנת 1970 בקושי ניתן היה לפרק מספר בן 20 ספרות עשרוניות, הרי שתוך פחות מעשור לאחר מכן חלה התקדמות משמעותית.
ב-1980 הצליחו ג'ון ברילהרט ומייקל מוריסון לפרק לגורמים מספר בן 50 ספרות עשרוניות באמצעות שברים משולבים בהתבסס על רעיון של מאוריס קרייצ'יק. ב-1990 הצליח צוות מתמטיקאים לפרק לגורמים מספר בן 116 ספרות עשרוניות תוך שימוש באלגוריתם הנפה הריבועית של קרל פומרנץ ובשנת 1994 באמצעות אותו אלגוריתם פורק בהצלחה מספר האתגר RSA-129. במאי 2005 הסתיים באוניברסיטת בון מאמץ ממושך שהחל בסוף 2003 בפירוק המספר RSA-200 (כ-663 סיביות) לגורמים. הפירוק בוצע באמצעות אלגוריתם נפת שדה מספרים הכללי של ג'ון פולרד, האחים לנסטרה (הנדריק וארג'ן) ומרק מאנס, בזמן של 55 שנות מעבד אופטרון 2.2GHz יחיד, על ידי צוות מתמטיקאים בראשות בוהר, בוהם, פרנק וקלנג'ונג. זהו המספר הגדול ביותר שפורק לגורמים נכון לשנת 2008. בנובמבר 2005 הצליח אותו צוות עם אותו אלגוריתם לפרק לגורמים את המספר RSA-640 (בגודל 193 ספרות עשרוניות) במאמץ של כ-30 שנות מעבד אופטרון 2.2GHz במשך חמישה חודשים, כמחצית מן הזמן שנדרש לפירוק RSA-200.

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

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

אלגוריתמים מתקדמים

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

אלגוריתמים קוונטיים

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