Liczby RSA

Liczby RSA to lista dużych liczb pseudopierwszych opublikowanych przez RSA Security w marcu 1991 roku w ramach zawodów RSA Factoring Challenge. Za rozłożenie na czynniki pierwsze niektórych z nich została wyznaczona nagroda pieniężna. Poniżej przedstawione są niektóre z tych liczb, wraz z informacją kto i w jaki sposób dokonał ich faktoryzacji.

RSA-576

RSA-576 została rozłożona na czynniki pierwsze przy użyciu algorytmu GNFS, 3 grudnia 2003 przez J. Franke i T. Kleinjunga z Uniwersytetu w Bonn.

Faktoryzacja RSA-576 wygląda następująco:

RSA-576 = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319
          060606504743045317388011303396716199692321205734031879550656996221305168759307650257059

RSA-576 = 398075086424064937397125500550386491199064362342526708406385189578636388957261768583317
        * 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527

RSA-640

RSA-640 została rozłożona na czynniki pierwsze przy użyciu algorytmu GNFS, 2 listopada 2005 przez zespół z Uniwersytetu w Bonn. Za rozłożenie tej liczby zespół odebrał ustanowioną wcześniej nagrodę 20.000 $.

Faktoryzacja RSA-640 wygląda następująco:

RSA-640 = 31074182404900437213507500358885679300373460228427275457
          20161948823206440518081504556346829671723286782437916272
          83803341547107310850191954852900733772482278352574238645
          4014691736602477652346609

RSA-640 = 16347336458092538484431338838650908598417836700330923121
          81110852389333100104508151212118167511579
        * 19008712816648221131268515739354139754718967899685154936
          66638539088027103802104498957191261465571

Obliczenie jej zajęło 5 miesięcy pracy osiemdziesięciu procesorom Opteron 2,2 GHz.

RSA-200

Ta sama grupa, również za pomocą algorytmu GNFS, 9 maja 2005 r. rozłożyła RSA-200, liczbę o 200 cyfrach dziesiętnych, czyli o 663 bitach, za którą jednak nie wyznaczono nagrody.

Faktoryzacja RSA-200 wygląda następująco:

RSA-200 = 2799783391122132787082946763872260162107044678695542853756000992932612840010
          7609345671052955360856061822351910951365788637105954482006576775098580557613
          579098734950144178863178946295187237869221823983

RSA-200 = 3532461934402770121272604978198464368671197400197625023649303468776121253679
          423200058547956528088349
        * 7925869954478333033347085841480059687737975857364219960734330341455767872818
          152135381409304740185467

RSA-704

RSA-704 została rozłożona na czynniki pierwsze 2 lipca 2012 przez zespół w składzie: Shi Bai, Emmanuel Thomé i Paul Zimmermann. Za jej rozłożenie RSA Security ustanowiło nagrodę 30.000 $, która jednak była aktualna tylko do 2007 r.

Faktoryzacja RSA-704 wygląda następująco:

RSA-704 = 74037563479561712828046796097429573142593188889231289084936232638972765034
          02826627689199641962511784399589433050212758537011896809828673317327310893
          0900552505116877063299072396380786710086096962537934650563796359

RSA-704 = 90912135295978188784406583026004374858926083103283587204285121689604115286
          40933367824950788367956756806141
        * 81438592591100452657278091262844293358778990021676278832009141724293243601
          33004116702003240828777970252499

RSA-768

RSA-768 została rozłożona na czynniki pierwsze 12 grudnia 2009 po ponad 2 latach pracy zespołu w składzie: Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos, Dag Arne Osvik, Herman te Riele, Andrey Timofeev i Paul Zimmermann.

Faktoryzacja RSA-768 wygląda następująco:

RSA-768 = 12301866845301177551304949583849627207728535695953347921973224521517264005
          07263657518745202199786469389956474942774063845925192557326303453731548268
          50791702612214291346167042921431160222124047927473779408066535141959745985
          6902143413

RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793
          878002287614711652531743087737814467999489
        * 36746043666799590428244633799627952632279158164343087642676032283815739666
          511279233373417143396810270092798736308917

Obliczenie jej zajęło w przeliczeniu prawie 2000 lat przetwarzania na jednordzeniowym procesorze Opteron 2,2 GHz.

Linki zewnętrzne

• RSA Factoring Challenge: RSA-640. rsasecurity.com. [zarchiwizowane z tego adresu (2007-01-04)].
• Announcement of factorisation. crypto-world.com. [zarchiwizowane z tego adresu (2008-06-16)].
• Mathworld article, Eric W. Weisstein, 8 listopada 2005.
• MathWorld: RSA-576 factored
• Repost of an announcement email to the primenumbers Yahoo! group
• RSA Labs' take on the factorization. rsasecurity.com. [zarchiwizowane z tego adresu (2006-12-24)].
• RSA Factoring Challenge: RSA-704. rsasecurity.com. [zarchiwizowane z tego adresu (2006-12-09)].