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

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

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

ידיעת הפירוק לגורמים ראשוניים של מספר מסוים מספקת ידיעה מלאה על כל מחלקיו של מספר זה. דוגמה: הפירוק לגורמים של המספר 6936 המופיע לעיל מלמד אותנו שכל מחלק של מספר זה הוא מהצורה $2^{a}\cdot 3^{b}\cdot 17^{c}$ כאשר $0\leq a\leq 3,0\leq b\leq 1,0\leq c\leq 2$.
זה מביא אותנו ל-3 · 2 · 2 · 2 = 24 מחלקים בסך הכל.

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

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

עד אמצע המאה ה-20 הבעיה העסיקה מעטים שהתמידו בחיפוש שיטות יעילות יותר לפירוק מספרים גדולים לגורמים. בחצי השני של המאה העשרים, עם התפתחות המחשבים ועלייתה של הקריפטוגרפיה, במיוחד מערכות אבטחה אסימטריות שמסתמכות על פירוק לגורמים ככלי הצפנה כמו RSA ודומיה, עלתה רמת העניין בבעיה זו. כיום הבעיה נחשבת לאחת הבעיות החשובות בתורת המספרים והיא מעסיקה מתמטיקאים רבים מכל העולם. חשיבותה נודעת לא רק מהיבט קריפטוגרפי אלא בעיקר כבעיה חישובית המשמשת כמדד יכולת וידע טכנולוגי. חברת RSA פירסמה בעבר רשימת מספרים שהם כפולה של שני ראשוניים גדולים, שהציבה כאתגר לציבור עם פרס בצידם למי שיצליח לפרקם לגורמים. מספרים אילו מכונים מספרי האתגר של RSA ומיוצגים על ידי RSA-xxxx כשה-xים מציינים את מספר הספרות (בבסיס בינארי, ולעיתים בבסיס עשר). למשל הפרס למי שיצליח לפרק לגורמים את המספר RSA-2048 (בגודל 617 ספרות עשרוניות) היה 200,000 דולר. אולם פרויקט האתגר בוטל בראשית 2008.

לפני שלוש מאות שנה, שיער המתמטיקאי הצרפתי מרן מרסן שהמספר $\ 2^{251}-1$ פריק. 100 שנים מאוחר יותר הוכח שהוא צדק, עם זאת אפילו רק לפני כשני עשורים, המאמץ שנדרש לפירוק מספר זה היה כמעט מעבר ליכולת הטכנולוגית באותה עת. ב-1984 ההערכה הייתה שלפירוק המספר יידרשו $\ 10^{20}$ שנים בקירוב. המספר פורק בהצלחה באותה שנה בתוך 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.

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

מספרי פרמה $\ F_{k}=2^{2^{k}}+1$ קרויים על שמו של פייר דה פרמה, שהתעניין בפירוק לגורמים בשל הקשר למספרים משוכללים ומספרים ידידים. הוא טען והוכיח, כי מספרים מהצורה $\ 2^{m}+1$ יכולים להיות ראשוניים רק אם $\ m$ הוא חזקה של $\ 2$. הוא האמין שמספרים אלו ראשוניים כולם. כיום ידוע שלא, למשל $\ F_{5}=2^{2^{5}}+1$ מתחלק ב-641, אם כי פרמה עצמו החמיץ עובדה זו מסיבה לא ידועה. שנים לאחר מכן הוכיח גאוס את חשיבות מספרי פרמה בגאומטריה אלמנטרית, ומתמטיקאים רבים ניסו כוחם בפירוק מספרי פרמה תוך שימוש במיטב האלגוריתמים הידועים בתקופתם.

הבעיה הורחבה לבעיה כללית יותר של פירוק מספרים מהצורה $\ b^{m}\pm 1$ (כאשר $\ b$ קטן ו-$\ m$ גדול), מספרים אילו מכונים מספרי קנינגהם על שם המתמטיקאי אלן ג'וזף קנינגהם (Allan J. C. Cunningham). פרויקט קנינגהם היווה מעין מבחן כוח להתקדמות בתחום הכללי של פירוק לגורמים. ב-1880 מצאו מתמטיקאים את הגורמים הראשוניים של $\ F_{6}$, רק כמאה שנים לאחר מכן ב-1970 הצליחו מוריסון וברילהרט לפרק את $\ F_{7}$ באמצעות שברים משולבים. מספר פרמה השמיני פורק ב-1980 על ידי ברנט ופולרד באמצעות גרסה של אלגוריתם rho של פולרד היעיל במיוחד במציאת גורמים קטנים. מספר פרמה התשיעי פורק לחלוטין ב-1990 על ידי האחים לנסטרה, מאנאס ופולרד שעשו זאת במאמץ שנמשך כארבעה חודשים, באמצעות נפת שדה המספרים והשתמשו בכוח חישוב של כשבע מאות מחשבים שגויסו ממקומות שונים ברחבי העולם ומחשב-על אחד שריכז את העבודה. מספר פרמה העשירי פורק לגורמים ב-1999 על ידי ריצ'רד ברנט באמצעות שיטת העקום האליפטי. ב-1988 נעשה שימוש באותה שיטה כדי לפרק לגורמים את $\ F_{11}$ (שגורמיו הראשוניים (פרט לגדול ביותר) נמצאו כולם קטנים). עד היום (2010), נמצאו כ-250 גורמים ראשוניים של מספרי פרמה מ-$\ F_{12}$ עד $\ F_{2478782}$, כאשר מספר פרמה הקטן ביותר שעדיין לא ידוע האם הוא פריק או ראשוני הוא $\ F_{33}$. אך פירוקם המלא של מספרים אלו לגורמים טרם צלח.

חשיבותם של מספרי קנינגהם כמדד יעילות בפירוק לגורמים הולכת ודועכת לאחרונה, מהסיבה הפשוטה שהמספרים שיש בהם עניין מיוחד כיום (המשמשים בדרך כלל במערכות הצפנה) קשים בהרבה לפירוק ממספרי פרמה המקבילים להם. למשל מודלוס בגודל 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) בתוך חמש דקות, אולם כבכל תחרות הרעיון היה למצוא את הטריק שיקצר את הדרך משמעותית. התשובה פשוטה; ניתן להציג את המספר $\ 8051$ גם כהפרש $\ 8100-49=90^{2}-7^{2}$, ולכן $\ 8051=(90+7)\cdot (90-7)=97\cdot 83$. על טריק זה המכונה הפרש ריבועים, מבוססת שיטת הפירוק לגורמים של המתמטיקאי הצרפתי פרמה. קל להבין זאת אם זוכרים שכל מספר פריק אי-זוגי ניתן לייצוג כהפרש הריבועים:

$\ ab=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{2}$.

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

קרייצ'יק העלה רעיון לשיפור שיטת פרמה, מה שהפך לאחר מכן כבסיס למרבית האלגוריתמים המודרניים. במקום למצוא שלמים $\ u,v$ המקיימים $\ u^{2}-v^{2}=n$ עבור השלם $\ n$ אותו אנו מעוניינים לפרק, מספיק למצוא שלמים כאלו שהם כפולה של $\ n$ כלומר $\ u^{2}\equiv v^{2}\ ({\mbox{mod }}n)$. לשקילות האחרונה יכולים להיות שני פתרונות, האחד 'אינו מעניין' כאשר $\ u\equiv \pm v\ ({\mbox{mod }}n)$ ושני 'מעניין' כאשר $\ u\not \equiv \pm v\ ({\mbox{mod }}n)$. האחרון מעניין כיוון שלפחות למחצית השלמים הזרים ל-$\ n$ קיים פתרון כזה אם $\ n$ אי זוגי ומתחלק לכל הפחות בשני ראשוניים שונים. וזה מעניין משום שהמחלק המשותף המרבי של $\ n$ ו-$\ u-v$ הוא גורם ראשוני של $\ n$. זאת משום ש-$\ n$ הוא מחלק של $\ u^{2}-v^{2}=(u-v)(u+v)$, אולם אינו מחלק אף גורם מהם (כלומר את $\ u$ או את $\ v$ עצמם), עובדה זו מעידה על כך ש-$\ n$ נמצא היכן שהוא בין $\ u-v$ ל-$\ u+v$.

לדוגמה אם $\ n=2041$, המספר הריבועי הסמוך ל-$\ n$ מעליו הוא $\ 46^{2}=2116$. אם נגדיר פולינום ממעלה שנייה $\ Q(x)=x^{2}-n$ עבור השלמים $\ x=46,47,48,...$ נקבל את התוצאות $\ 75,168,263,360,459,560,...$. אמנם עדיין לא נמצא מספר ריבועי כלשהו אולם הרעיון הוא למצוא מספר שלמים $\ x$ כאלו המקיימים:

$\ Q(x_{1})\cdot Q(x_{2})\cdots Q(x_{k})=v^{2}$ וכן

$\ x_{1}\cdot x_{2}\cdots x_{k}=u$ ואז

$\ u^{2}=x_{1}^{2}\cdot x_{2}^{2}\cdots x_{k}^{2}\equiv (x_{1}^{2})\cdot (x_{2}^{2}-n)\cdots (x_{k}^{2}-n)=Q(x_{1})\cdot Q(x_{2})\cdots Q(x_{k})=v^{2}\ ({\mbox{mod }}n)$.

הפתרון ל-$\ u^{2}\equiv v^{2}\ ({\mbox{mod }}n)$ כעת ברור. אולם כיצד למצוא $\ x$ים כאלו שכפולת הפולינומים מעליהם נותנת מספר ריבועי? הרעיון של קרייצ'יק הוא שחלק מהפולינומים $\ Q(x)$ ניתנים לפירוק לגורמים יחסית בקלות, כפי שרואים: $\ 75=3\cdot 5^{2},168=2^{3}\cdot 3\cdot 7,360=2^{3}\cdot 3^{2}\cdot 5$ וכן $\ 560=2^{4}\cdot 5\cdot 7$. מתוך הפירוק של ארבעה מספרים אילו אפשר לראות ש-$\ 2^{10}\cdot 3^{4}\cdot 5^{4}\cdot 7^{2}$ הוא מספר ריבועי וכך מצאנו את $\ u^{2}\equiv v^{2}\ ({\mbox{mod }}n)$ כאשר:

$\ u=46\cdot 47\cdot 49\cdot 51=311{\mbox{ mod }}2041$ וכן

$\ v=2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7=1416{\mbox{ mod }}2041$.

הרעיון כמעט הושלם, היות ש-$\ 311\not \equiv \pm 1416{\mbox{ mod }}2041$, אפשר להשתמש באלגוריתם אוקלידס לחישוב מחלק משותף מקסימלי של $\ (1416-311,2041)$ ומצאנו ש-$\ 2041=13\cdot 157$. איך ידענו למצוא את ה-$\ x$ים הנכונים? הרעיון של קרייצ'יק היה פשוט לחפש אותם סדרתית. אלגוריתם קרייצ'יק פותח לאחר מכן על ידי מספר מתמטיקאים, הצעה אחת הייתה להחליף את הפונקציה $\ Q(x)=x^{2}-n$ בפונקציה עדיפה הנובעת מהרחבה של השברים המשולבים של שורש $\ n$. מסתבר שחיפוש יעיל של סדרה כזו של $\ x$ים המקיימת את התנאי האמור היא בעצם המשימה העיקרית בכל אלגוריתם לפירוק לגורמים.

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

קרל פומרנץ ניצל את האסטרטגיה של ברילהרט ומוריסון כדי לפתח על בסיס שיטת קרייצ'יק את אלגוריתם הנפה הריבועית. הדרך למצוא סדרה המניבה מספר ריבועי נעשית באמצעות אלגברה לינארית. אם מתייחסים לוקטור $\ v(m)$ כוקטור של מעריכים של הגורמים של $\ m$, אזי אפשר לראות שרק אם סכום המעריכים זוגי יתקבל מספר ריבועי. לכן התכסיס הוא לחפש מספרים שניתן לייצגם ככפולה של סדרה קטנה של חזקות ראשוניים אותה מכנים 'בסיס גורמים'. אפשר ל'שחק' בכמה מספרים כאלו עד שעולים על תלות לינארית של וקטור המעריכים (כלומר וקטור שסכומו אפס) ומשם הדרך למציאת מספר ריבועי מתאים קלה. במרוצת הזמן נוספו עוד שיפורים לאלגוריתם הנפה הריבועית על ידי מתמטיקאים רבים.

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

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

בהנחה שמחשבים קוונטיים בקנה מידה מלא יהיו מעשיים בזמן הקרוב ניתן יהיה לפרק כל מספר גדול לגורמים בסיבוכיות זמן של $\ O(\log ^{3}(n))$ באמצעות אלגוריתם שור. לעובדה זו השלכות מרחיקות לכת על תורת ההצפנה וכבר בימינו שוקדים מדענים על פיתוח אלגוריתמים פוסט-קוונטיים שיעמדו בפני קריפטואנליזה על מחשב קוונטי כאשר יהיה מעשי. ההערכות מדברות על פחות מ-15 שנה. נכון לשנת 2015 המחשב הקוונטי הגדול ביותר הוא בקנה מידה של 1000 קיוביטים. מהיבט של קריפטוגרפיה זה די נמוך מהגודל הדרוש כדי לפרק לגורמים מספרים בהם משתמשים במערכות הצפנה מודרניות.

ראו גם

• שבר חלקי
• נפה ריבועית - שיטה מהירה לפירוק מספרים לגורמים, המתאימה בעיקר למספרים בני 40–100 ספרות עשרוניות.
• אלגוריתם שור - אלגוריתם קוונטי לפירוק מספר לגורמים.
• פירוק לגורמים עבור המושג הכללי.

קישורים חיצוניים

• המאמר A Tale of Two Sieves של קרל פומרנץ ממציא הנפה הריבועית ונמנה עם מפתחי NFS.
• פירוק לגורמים, מתוך סיכומונה