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

במתמטיקה, פירוק לגורמים של מספר שלם הוא פירוקו של המספר למספרים קטנים יותר, הקרויים גורמים, כך שמכפלת הגורמים זה בזה תתן את המספר המקורי. לדוגמה, את המספר 6936 ניתן לפרק לגורמים ראשוניים 172 · 3 · 23 = 6936.

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

ידיעת הפירוק לגורמים ראשוניים של מספר מסוים מספקת ידיעה מלאה על כל מחלקיו של מספר זה. דוגמה: הפירוק לגורמים של המספר 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.