RSA-числа — это множество больших полупростых чисел (чисел, представимых в виде произведения двух простых чисел), используемых в конкурсе RSA Factoring Challenge. Конкурс заключался в нахождении простых множителей предложенных чисел, но в 2007 году был объявлен неактивным. RSA Factoring Challenge был запущен по инициативе RSA Laboratories в марте 1991 года для поощрения исследований в области вычислительной теории чисел и практической сложности факторизации больших целых чисел.
RSA Laboratories опубликовала 54 полупростых числа длиной от 100 до 617 десятичных знаков. За факторизацию некоторых из них были предложены денежные призы. Наименьшее RSA-число было разложено за несколько дней. Большинство чисел до сих пор не разложено и предполагается, что многие из них останутся неразложенными ещё довольно долгое время.
RSA Challenge официально закончился в 2007 году, но люди до сих пор пытаются раскладывать числа, к апрелю 2020 года было разложено 22 из 54 чисел. Первые RSA-числа, от RSA-100 до RSA-500, были пронумерованы в соответствии с числом десятичных знаков. Более поздняя нумерация отражает число битов (даже для чисел, попадающих в первый диапазон). Ниже приведён список RSA-чисел в порядке возрастания.
RSA-100 RSA-100 имеет 100 десятичных знаков (330 бит). О его разложении на простые множители объявил Арьен Ленстра 1 апреля 1991 года. По сообщениям, разложение заняло несколько дней, в качестве алгоритма факторизации использовался метод квадратичного решета, а вычисления проводились на компьютере MasPar.
Числовое значение и разложение RSA-100 следующие:
RSA-100 = 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
RSA-100 = 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061
Повторение этого разложения с использованием программы Msieve занимает около 14 часов на процессоре Athlon 64 2200 МГц.
RSA-110 RSA-110 имеет 110 десятичных знаков (364 бита) и было факторизовано в апреле 1992 года Арьеном Ленстрой и Марком Менесси примерно за месяц.
Число и его разложение на множители:
RSA-110 = 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
RSA-110 = 6122421090493547576937037317561418841225758554253106999 × 5846418214406154678836553182979162384198610505601062333
RSA-120 RSA-120 имеет 120 десятичных знаков (397 бит) и было разложено в июне 1993 года Томасом Денни, Брюсом Додсоном, Арьеном Ленстрой и Марком Менесси. Вычисления заняли около трёх месяцев машинного времени.
Числовое значение и разложение на множители:
RSA-120 = 227010481295437363334259960947493668895875336466084780038173258247009162675779735389791151574049166747880487470296548479
RSA-120 = 327414555693498015751146303749141488063642403240171463406883 × 693342667110830181197325401899700641361965863127336680673013
RSA-129 RSA-129 имеет 129 десятичных знаков (426 бит) и не было частью 1991 RSA Factoring Challenge.
RSA-129 было разложено в апреле 1994 года командой, возглавляемой Дереком Аткинсом, Майклом Граффом, Арьеном Ленстрой и Полом Лейландом с использованием примерно 1600 компьютеров около 600 добровольцев, соединённых через сеть Интернет. Полученные за разложение 100 долларов США были пожертвованы Фонду свободного программного обеспечения.
Числовое значение и факторизация:
RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577 × 32769132993266709549961988190834461413177642967992942539798288533
Факторизация была проведена с использованием метода квадратичного решета.
Соревнование по разложению числа включало сообщение, зашифрованное с RSA-129. После расшифровки, использующей факторизацию, было получено «The Magic Words are Squeamish Ossifrage» («Волшебные слова — это брезгливый ягнятник»).
RSA-130 RSA-130 имеет 130 десятичных знаков (430 битов) и было разложено 10 апреля 1996 года командой под руководством Арьена Ленстры, состоявшей из Джима Коуи, Элькенбрахта-Гуйцинга, Вожтека Фурмански, Питера Монтгомери, Дамиана Вебера и Джоерга Заера.
Числовое значение и факторизация:
RSA-130 = 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557
RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243 × 45534498646735972188403686897274408864356301263205069600999044599
Разложение было найдено с использованием общего метода решета числового поля и многочлена
5748302248738405200 x5 + 9882261917482286102 x4 - 13392499389128176685 x3 + 16875252458877684989 x2 + 3759900174855208738 x - 46769930553931905995,
который имеет корень 12574411168418005980468 по модулю RSA-130.
RSA-140 RSA-140 имеет 140 десятичных знаков (463 бита) и было разложено 2 февраля 1999 года командой, возглавлявшейся Германом Рилем и состоявшей из Стефании Каваллар, Брюса Додсона, Арьена Ленстры, Пола Лейланда, Уолтера Лиоена, Питера Монтгомери, Брайана Мерфи и Поля Циммерманна.
Числовое значение и факторизация:
RSA-140 = 21290246318258757547497882016271517497806703963277216278233383215381949984056495911366573853021918316783107387995317230889569230873441936471
RSA-140 = 3398717423028438554530123627613875835633986495969597423490929302771479 × 6264200187401285096151654948264442219302037178623509019111660653946049
При разложении использовался общий метод решета числового поля и затрачено 2000 MIPS-лет.
RSA-150 RSA-150 имеет 150 десятичных знаков (496 бит) и было снято с соревнования RSA Security. RSA-150 было в конечном счёте разложено на два простых 75-значных числа в 2004 году с использованием общего метода решета числового поля, уже годами позже других, больших, RSA-чисел, которые были все ещё частью соревнования.
Числовое значение и факторизация:
RSA-150 = 155089812478348440509606754370011861770654545830995430655466945774312632703463465954363335027577729025391453996787414027003501631772186840890795964683
RSA-150 = 348009867102283695483970451047593424831012817350385456889559637548278410717 × 445647744903640741533241125787086176005442536297766153493419724532460296199
RSA-155 RSA-155 имеет 155 десятичных знаков (512 бит) и было разложено 22 августа 1999 года командой, возглавлявшейся Германом Рилем и состоявшей из Стефании Каваллар, Брюса Додсона, Арьена Ленстры, Уолтера Лиоена, Питера Монтгомери, Брайана Мерфи, Карен Аардал, Джеффа Гилчриста, Жерара Гилема, Пола Лейланда, Джоэла Марчанда, Франсуа Морэна, Алека Маффетта, Крейга Патнема, Криса Патнема и Поля Циммермана.
Числовое значение и факторизация:
RSA-155 = 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897
RSA-155 = 102639592829741105772054196573991675900716567808038066803341933521790711307779 × 106603488380168454820927220360012878679207958575989291522270608237193062808643
Разложение было осуществлено с использованием общего метода решета числового поля и заняло 8000 MIPS-лет машинного времени.
RSA-160 RSA-160 имеет 160 десятичных знаков (530 бит) и было разложено 1 апреля 2003 года командой из Боннского университета и Федеральным управлением по информационной безопасности Германии. Команда состояла из Йенса Франке, Ф. Бара, Торстена Клейнжунга, М. Лохтера и М. Бома.
Числовое значение и факторизация:
RSA-160 = 2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753
RSA-160 = 45427892858481394071686190649738831656137145778469793250959984709250004157335359 × 47388090603832016196633832303788951973268922921040957944741354648812028493909367
При разложении использовался общий метод решета числового поля.
RSA-170 RSA-170 имеет 170 десятичных знаков (563 бита) и было разложено 29 декабря 2009 года Д. Боненбергером и М. Кроне из Fachhochschule Braunschweig/Wolfenbüttel.
Числовое значение и факторизация:
RSA-170 = 26062623684139844921529879266674432197085925380486406416164785191859999628542069361450283931914514618683512198164805919882053057222974116478065095809832377336510711545759
RSA-170 = 3586420730428501486799804587268520423291459681059978161140231860633948450858040593963 × 7267029064107019078863797763923946264136137803856996670313708936002281582249587494493
Разложение было найдено с помощью общего метода решета числового поля.
RSA-576 RSA-576 имеет 174 десятичных знака (576 бит) и было разложено 3 декабря 2003 года Йенсом Франке и Т. Клейнжунгом из Боннского университета. Денежный приз в 10 000 долларов США был объявлен RSA Security за успешную факторизацию.
Числовое значение и факторизация:
RSA-576 = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
RSA-576 = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 × 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
Разложение было найдено с использованием общего метода решета числового поля.
RSA-180 RSA-180 имеет 180 десятичных знаков (596 битов) и было разложено 8 мая 2010 года С. А. Даниловым и И. А. Поповяном из МГУ.
RSA-180 = 191147927718986609689229466631454649812986246276667354864188503638807260703436799058776201365135161278134258296128109200046702912984568752800330221777752773957404540495707851421041
RSA-180 = 400780082329750877952581339104100572526829317815807176564882178998497572771950624613470377 × 476939688738611836995535477357070857939902076027788232031989775824606225595773435668861833
Факторизация была проведена с использованием общего метода решета числового поля, реализация которого была запущена на трёх PC с Intel Core i7.
RSA-190 RSA-190 имеет 190 десятичных знаков (629 бит) и было разложено И. А. Поповяном из МГУ и А. П. Тимофеевым из центра математики и информатики, Нидерланды.
RSA-190 = 1907556405060696491061450432646028861081179759533184460647975622318915025587184175754054976155121593293492260464152630093238509246603207417124726121580858185985938946945490481721756401423481
RSA-190 = 31711952576901527094851712897404759298051473160294503277847619278327936427981256542415724309619 × 60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899
RSA-640 RSA-640 имеет 640 бит (193 десятичных знака). 2 ноября 2005 года Ф. Бар, М. Бом, Йенс Франке и Т. Клайнйунг из Федерального управления по информационной безопасности Германии объявили, что они разложили данное число, используя общий метод решета числового поля:
RSA-640 = 3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609
RSA-640 = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579 × 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571
Вычисления заняли 5 месяцев на 80 процессорах 2,2 ГГц AMD Opteron.
В мае 2005 года той же командой было разложено немного большее число — RSA-200.
RSA-200 RSA-200 имеет 200 десятичных знаков (663 бита), и представляет собой произведение двух простых 100-значных чисел, указанных ниже.
9 мая 2005 года Ф. Бар, М. Бом, Йенс Франке и Т. Клейнжунг объявили, что они разложили данное число, используя общий метод решета числового поля:
RSA-200 = 27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983