RSA faktorizazio-lehia

RSA faktorizazio-lehia zenbakien teoria konputazionalaren eta zenbaki handien faktorizazioaren ikerketa sustatzeko asmoz RSA Security enpresak 1991ko martxoaren 18an abian jarritako lehiaketa da. Zenbaki erdilehenen (bi zenbaki lehenen biderkadura diren zenbakiak) zerrenda bat argitaratu zuten, RSA zenbaki izenez ezagutzen direnak, eta haietako batzuk faktorizatzea lortzen zuenarentzat diru-saria eskaini zuten. Zerrenda argitaratu eta egun gutxira zerrendako zenbakirik txikiena faktorizatzea lortu zen: RSA-100 zenbakia zen, 100 zifra hamartarreko RSA zenbakia. Zerrendako zenbaki handienak oraindik faktorizatu gabe daude eta luzaroan horrela egongo direla uste da. Dena den, konputazio kuantikoari esker arlo honetan aurrerakuntza handiak egotea espero da.

RSA faktorizazio-lehia 2007an amaitu zen. Ordutik aurrera enpresak ez du saririk eskaini RSA zenbakiren bat faktorizatzea lortzeagatik. Izan ere, ordurako Kriptografia asko garatu zela ikusita, lehiaketa dagoeneko beharrezkoa ez zela erabaki zuten. Lehiaketarekin lortu zen kriptografia asimetrikokoko RSA gakoen luzera finkatzea, RSA bidezko kriptografia segurua izango baita RSA zenbakia faktorizatzea ezinezkoa denean. RSA Security enpresak RSA zifratze-algoritmoan oinarritutako produktuak saltzen zituenez, haien produktuen sendotasuna frogatzeko baliogarria izan zitzaien lehiaketa.

RSA zenbakien zerrenda osatzeko, zenbakiak sarera konektatu gabeko konputagailu batean sortzen ziren eta ondoren konputagailuaren disko gogorra suntsitu egiten zuten. Horrela, lehiaketaren soluzioak ez ziren inon gordeta geratuko eta sekretu izaten jarraituko zuten.

Faktorizatu ziren lehen RSA zenbakiak RSA-100etik RSA-500era bitartekoak eta RSA-617 izan ziren. Zenbaki horiek duten zifra hamartar kopuruaren arabera izendatu ziren (RSA-500 zenbakia, adibidez, 500 zifra hamartar dituen zenbakia da). Gainerako RSA zenbakiak gerora sortu zituzten eta duten zifra bitar kopuruaren arabera izendatu ziren.

 Matematika 
RSA zenbaki bat emanik, n, beti existituko dira bi zenbaki lehen p eta q, non zera betetzen den:

n = p × q

n zenbakia emanik, p eta q zenbakiak aurkitzean datza RSA zenbakien faktorizazioaren problema. n zenbakia oso handia denean, haren faktorizazioa zaila da, konputazionalki eraginkorra den algoritmorik ez dagoelako.

 Sariak eta errekorrak 
Hurrengo taulan RSA zenbakien ikuspegi orokorra ikus daiteke:

Txuriz ageri diren errenkadetako RSA zenbakiak adierazpen hamartarrean duten zifra kopuruaren arabera daude izendatuta. Gainerakoak, haien adierazpen bitarrean duten zifra kopuruaren arabera. Azken horietatik RSA-576 eta RSA-640 zenbakiak bakarrik izan ziren sarituak.
 RSA zenbakia Zifra hamartarrak Zifra bitarrak Diru-saria Noiz faktorizatua Nork faktorizatua RSA-100 100 330 US$1,000http://www.ontko.com/~rayo/primes/rsa_news.txt 1991ko apirilaren 1eanRSA Honor Roll Arjen K. Lenstra RSA-110 110 364 US$4,429 1992ko apirilaren 14an  Arjen K. Lenstra eta M.S. Manasse RSA-120 120 397 $5,898 1993ko uztailaren 9an On the factorization of RSA-120 - Springer. Springerlink.com. Retrieved on 2014-05-11. T. Denny et al. RSA-129  129 426 US$100 1994ko apirilaren 26an  Arjen K. Lenstra et al. RSA-130 130 430 US$14,527 1996ko apirilaren 10ean Arjen K. Lenstra et al. RSA-140 140 463 US$17,226 1999ko otsailaren 2an Herman te Riele et al. RSA-150 150 496   2004ko apirilaren 16an Kazumaro Aoki et al. RSA-155 155 512 $9,383 1999ko abuztuaren 22an Herman te Riele et al. RSA-160 160 530   2003ko apirilaren 1ean Jens Franke et al., Bonneko Unibertsitatea RSA-170  170 563   2009ko abenduaren 29an D. Bonenberger eta M. Krone  RSA-576 174 576 US$10,000 2003ko abenduaren 3an Jens Franke et al., Moskuko Estatu Unibertsitatea RSA-180  180 596   2010eko maiatzaren 8an S. A. Danilov eta I. A. Popovyan, Moskuko Estatu Unibertsitateahttp://eprint.iacr.org/2010/270.pdf RSA-190  190 629   2010eko azaroaren 8an A. Timofeev eta I. A. Popovyan RSA-640 193 640 US$20,000 2005eko azaroaren 2an Jens Franke et al., Bonneko Unibertsitatea RSA-200  200 663   2005eko maiatzaren 9an Jens Franke et al., Bonneko Unibertsitatea RSA-210  210 696 2013ko irailaren 26anRSA-210 factored, mersenneforum.org Ryan Propper RSA-704  212 704 US$30,000 2012ko otsailaren 2an  Shi Bai, Emmanuel Thomé eta Paul Zimmermann RSA-220  220 729   2016ko maiatzaren 13an S. Bai, P. Gaudry, A. Kruppa, E. Thomé eta P. Zimmermann RSA-230  230 762   2018ko abuztuaren 15ean Samuel S. Gross, Noblis, Inc. RSA-232 232 768   RSA-768  232 768 US$50,000 2009, abenduaren 12an Thorsten Kleinjung et al. RSA-240 240 795   2019, abenduaren 2an Fabrice Boudot et al. RSA-250 250 829   RSA-260 260 862   RSA-270 270 895   RSA-896 270 896 US$75,000 RSA-280 280 928   RSA-290 290 962   RSA-300 300 995   RSA-309 309 1024   RSA-1024 309 1024 US$100,000 RSA-310 310 1028   RSA-320 320 1061   RSA-330 330 1094   RSA-340 340 1128   RSA-350 350 1161   RSA-360 360 1194   RSA-370 370 1227   RSA-380 380 1261   RSA-390 390 1294   RSA-400 400 1327   RSA-410 410 1360   RSA-420 420 1393   RSA-430 430 1427   RSA-440 440 1460   RSA-450 450 1493   RSA-460 460 1526   RSA-1536 463 1536 US$150,000 RSA-470 470 1559   RSA-480 480 1593   RSA-490 490 1626   RSA-500 500 1659   RSA-617 617 2048   RSA-2048 617 2048 US$200,000

 Erreferentziak 

 Ikus, gainera 
 RSA
 Zenbaki lehen
 Faktorizazio
 Zenbaki osoen faktorizazio

 Kanpo estekak 
 RSA Security: The RSA factoring challenge
 MathWorld: RSA Number
 Mathematica package for RSA numbers
 The original challenge announcement on sci.crypt (updated link)

Kategoria:Kriptografia
Kategoria:Zenbakien teoria
Kategoria:Lehiaketak
Kategoria:Matematika sariak