שני דוגמאות: פירוק לגורמים ומחלקים משותפים

המחשבים הקלאסיים שקיימים היום הם מהירים להפליא, ומהירותם נראית כאילו רק הולכת וגדלה. מסיבה זו, יש שעשויים להאמין שמחשבים מהירים כל כך עד שאין שום בעיה חישובית שמחוץ להישגם.

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

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

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

קלט: מספר שלם $N\geq 2$
פלט: הפירוק לגורמים ראשוניים של $N$

בפירוק לגורמים ראשוניים של $N$ אנו מתכוונים לרשימת הגורמים הראשוניים של $N$ ולחזקות שאליהן יש להעלות אותם כדי לקבל את $N$ על ידי כפל. לדוגמה, הגורמים הראשוניים של $12$ הם $2$ ו-$3,$ וכדי לקבל $12$ עלינו לחשב את מכפלת $2$ בחזקת $2$ ו-$3$ בחזקת $1.$

$$12 = 2^2 \cdot 3$$

עד כדי סדר הגורמים הראשוניים, קיים פירוק ראשוני יחיד לכל מספר שלם חיובי $N\geq 2,$ עובדה הידועה בשם המשפט היסודי של האריתמטיקה.

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

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

הפונקציה factorint מחבילת המתמטיקה הסימבולית SymPy עבור Python פותרת את בעיית פירוק לגורמים שלמים עבור כל קלט $N$ שנבחר. לדוגמה, נוכל לקבל את הפירוק הראשוני של 12, שכמובן מסכים עם הפירוק לעיל.

N = 12
print(factorint(N))

{2: 2, 3: 1}

פירוק מספרים קטנים כמו $12$ הוא קל, אך כאשר המספר $N$ שיש לפרק גדל, הבעיה נעשית קשה יותר. לדוגמה, הרצת factorint על מספר גדול בהרבה גורמת לעיכוב קצר אך מורגש במחשב אישי טיפוסי.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

עבור ערכים גדולים עוד יותר של $N,$ הדברים הופכים לבלתי אפשריים, לפחות עד כמה שאנו יודעים. לדוגמה, אתגר הפירוק RSA, שהופעל על ידי RSA Laboratories בין 1991 ל-2007, הציע פרס כספי של $100,000 לפירוק המספר הבא, שיש לו 309 ספרות עשרוניות (או 1024 ביט כאשר כותבים אותו בבינארי). הפרס עבור מספר זה מעולם לא נגבה והגורמים הראשוניים שלו נותרים לא ידועים.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

אנחנו לא צריכים לטרוח להריץ את factorint על RSA1024 — זה לא יסתיים בתוך חיינו.

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

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

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

עכשיו בוא נסתכל על בעיה קשורה אך שונה מאוד, והיא חישוב המחלק המשותף הגדול ביותר (GCD) של שני מספרים שלמים.

מחלק משותף גדול ביותר (GCD)

קלט: מספרים שלמים לא שליליים $N$ ו-$M,$ לפחות אחד מהם חיובי
פלט: המחלק המשותף הגדול ביותר של $N$ ו-$M$

המחלק המשותף הגדול ביותר של שני מספרים הוא המספר השלם הגדול ביותר שמחלק את שניהם ללא שארית.

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

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

זה אפשרי מפני שיש לנו אלגוריתמים יעילים מאוד לחישוב מחלקים משותפים, הידוע שבהם הוא האלגוריתם של אוקלידס, שהתגלה לפני יותר מ-2,000 שנה.

האם ייתכן שקיים אלגוריתם מהיר לפירוק לגורמים שלמים שפשוט עוד לא גילינו, שיאפשר לפרק מספרים גדולים כמו RSA1024 בהינף עין? התשובה היא כן. אף שאולי היינו מצפים שאלגוריתם יעיל לפירוק, פשוט ואלגנטי כמו האלגוריתם של אוקלידס לחישוב מחלקים משותפים, היה מתגלה עד כה, אין שום דבר שמוציא מכלל אפשרות קיומו של אלגוריתם קלאסי מהיר מאוד לפירוק לגורמים שלמים, מעבר לעובדה שלא הצלחנו למצוא כזה עד כה. אפשר שמישהו יגלה כזה מחר — אבל אל תחזיקו את הנשימה. דורות של מתמטיקאים ומדעני מחשב חיפשו, ופירוק מספרים כמו RSA1024 נותר מחוץ להישגנו.