מספרי RSA
במתמטיקה, מספרי RSA הם קבוצה של סמי- ראשוניים גדולים (מספרים עם שני גורמים ראשוניים בדיוק) שהיו חלק מאתגר RSA Factoring . האתגר היה למצוא את הגורמים הראשוניים של כל מספר. הוא נוצר על ידי RSA Laboratories במרץ 1991 כדי לעודד מחקר של תורת המספרים החישובית והקושי המעשי של עיבוד מספרים שלמים גדולים. האתגר הסתיים בשנת 2007.[1]
RSA Laboratories (שהם ראשי תיבות של יוצרי הטכניקה; Rivest, שמיר ואדלמן) פרסמו מספר סמי-פריים עם 100 עד 617 ספרות עשרוניות. פרסים כספיים בגדלים שונים, עד 200,000 דולר ארצות הברית (ופרסים של עד 20,000 דולר), הוצעו לפירוק חלק מהם. מספר ה-RSA הקטן ביותר הוערך תוך מספר ימים. רוב המספרים עדיין לא הובאו בחשבון ורבים מהם צפויים להישאר ללא גורמים במשך שנים רבות. נכון לפברואר 2020, 23 מספרי הRSA הקטנים ביותר מתוך 54 המספרים המפורטים פורקו לגורמים.
בעוד שאתגר ה-RSA הסתיים רשמית ב-2007, אנשים עדיין מנסים למצוא את הפירוק לגורמים. לפי RSA Laboratories, "כעת, כאשר לתעשייה יש הבנה מתקדמת משמעותית של החוזק הקריפאנליטי של אלגוריתמים נפוצים של מפתח סימטרי ושל מפתח ציבורי, האתגרים הללו אינם פעילים עוד."[2] כמה מהפרסים הקטנים יותר הוענקו אז. שאר הפרסים בוטלו.
מספרי ה-RSA הראשונים שנוצרו, מ-RSA-100 עד RSA-500, סומנו לפי מספר הספרות העשרוניות שלהם. מאוחר יותר, החל מ-RSA-576, ספרות בינאריות נספרות במקום זאת. חריג לכך הוא RSA-617, שנוצר לפני השינוי בסכימת המספור. המספרים מפורטים בסדר עולה למטה.
| Contents | |||||
|---|---|---|---|---|---|
|
|
|
|
|
|
RSA-100
ל-RSA-100 יש 100 ספרות עשרוניות (330 סיביות). המספר פורק לגורמים ב 1 באפריל 1991 על ידי Arjen K. Lenstra . [3] [4] לפי הדיווחים, הפירוק לגורמים נמשך כמה ימים באמצעות אלגוריתם המסננת הריבועית המרובה-פולינומית במחשב מקביל של MasPar.[5]
הערך והפירוק לגורמים של RSA-100 הם כדלקמן:
RSA-100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
RSA-100 = 37975227936943673922808872755445627854565536638199× 40094690950920881030683735292761468389214899724061
לוקח ארבע שעות לחזור על הפירוק הזה באמצעות התוכנית Msieve ב-2200 מעבד Athlon 64 MHz.
ניתן לחלק את המספר לגורמים תוך 72 דקות ב-Overclock ל-3.5 GHz Intel Core 2 Quad q9300, באמצעות GGNFS ו Msieve הבינאריים פועל באמצעות גרסה מבוזרת של התסריט פרל factmsieve .[6]
RSA-110
ל-RSA-110 יש 110 ספרות עשרוניות (364 סיביות), והוא הופעל באפריל 1992 על ידי לנסטרה. כחודש אחד.[5] ניתן לחלק את המספר בפחות מארבע שעות ב-overclocked ל-3.5 GHz Intel Core 2 Quad q9300, באמצעות GGNFS ו Msieve הבינאריים פועל באמצעות גרסה מבוזרת של התסריט פרל factmsieve .[6]
RSA-110 = 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
RSA-110 = 6122421090493547576937037317561418841225758554253106999× 5846418214406154678836553182979162384198610505601062333
RSA-232
ל-RSA-232 יש 232 ספרות עשרוניות (768 סיביות), והוא הופעל ב-17 בפברואר 2020 על ידי NL Zamarashkin, DA Zheltkov ו-SA Matveev.[7]
RSA-232 = 1009881397871923546909564894309468582818233821955573955141120516205831021338528545374366109757154363664913380084917065169921701524733294389270280234380960909804976440540711201965410747553824948672771374075011577182305398340606162079
RSA-232 = 29669093332083606603617799242426306347429462625218523944018571574194370194723262390744910112571804274494074452751891× 34038161751975634380066094984915214205471217607347231727351634132760507061748526506443144325148088881115083863017669
RSA-480
ל-RSA-480 יש 480 ספרות עשרוניות (1,593 סיביות), והוא לא פורק לגורמים עד כה.
RSA-480 = 3026570752950908697397302503155918035891122835769398583955296326343059761445714416965981704012518521591385333455982172343712313383247732107268535247763784105186549246199888070331088462855743520880671299302895546822695492968577380706795842802200829411198422297326020823369315258921162990168697393348736236081296604185145690639952829781767901497605213955485328141965346769742597479306858645849268328985687423881853632604706175564461719396117318298679820785491875674946700413680932103