RSA Faktorizazio Lehiaketa[aldatu | aldatu iturburu kodea]

RSA faktorizazio lehiaketa 1991ko matrxoaren 18an jarri zuen habian RSA Security enpresak, zenbakien teoria konputazionala eta zenbaki handien faktorizazioa sustatzeko asmoz. Zenbaki semilehenen zerrenda bat argitaratu zuten, RSA zenbakiak bezela ezagutuak, diru-sariekin zenbaki horietako bat faktorizatzeagatik. Zerrenda argitaratu eta egun gutxitara lehen zenbakia faktorizatzea lortu zuten. Zenbaki hau RSA-100 bezela ezagutzen da eta 100 zifra hamartarreko zenbaki bat da. Zerrendako zenbaki handienak horaindik faktorizatu gabe daude, eta urte askotarako horrela jarraitzea espero da. RSA Security enpresak 2007an amaiarazi zen lehieaketa^[1].

Lehiaketa honetan zenbaki osoen faktorizazio inguruko aurrerapenak bilatzen zituen. Honen erabilera garrantzitsuenetako bat RSA enkriptatzean gakoen luzeera aukeratzeko orduan aurkitu daiteke, RSA gakoaren luzeeraren harabera oraindik segurua den edo ez jakiteko. RSA Security RSA-an oinarritutako produktuak saltzen zituzten, beraz lehiaketa hau beraien produktuen sendotasuna frogatzeko balio izan zien.

RSA zenbakiak sarera ez konektatutako ordenagailu batean sortzen ziren, eta gero ordenagailuaren disko gogorrra suntsitu egiten zen. Horrela lehiaketaren soluzioak ez ziren inon gordeta geratuko eta sekretu izaten jarraituko zuten^[1].

Lortutako lehen RSA zenbakiak RSA-100-etik RSA-500-era eta RSA-617 izan ziren. Zenbaki hauek bere digitu hamartarren kopuruaren harabera izendatu ziren (RSA-500, 500 digituko hamartarreko zenbakia). Hurrengo RSA zenbakiak beraien digitu bitar kopuruarekin izendatu ziren.

Matematika[aldatu | aldatu iturburu kodea]

RSA zenbaki bakotzarentzat bi zenbaki lehen egongo dira, p eta q, non beraien harteko biderketak zenbaki hori ematen duen, n :

n = p × q

Arazoa n zenbakia bakarrik emanda p eta q zenbakiak bilatzea da.

Errekorrak eta sariak[aldatu | aldatu iturburu kodea]

Hurrengo taulan RSA zenbaki guztien ikuspegi orokorra emango da:

Kaxa zurietako RSA zenbakiak beraien adierazpen hamartearreko zifra kopuruaren harabera daude zenbakituak. Besteak, beraien adierazpen bitarren zifra kopuruaren harabera. Azken hauetatik bakarrik RSA-576 eta RSA-640 zenbakiak izan ziren sarituak, besteak ez ziren inoiz saritu, lehiaketa 2007an amaitu zelako.

RSA Zenbakiak	Digitu hamartarak	Digitu bitarrak	Diru-saria	Noiz	Nork
RSA-100	100	330	US$1,000^[2]	1991ko Apirilaren 1an^[3]	Arjen K. Lenstra
RSA-110	110	364	US$4,429^[2]	1992ko Apirilaren 14an ^[3]	Arjen K. Lenstra eta M.S. Manasse
RSA-120	120	397	$5,898^[2]	1993ko Uztailaren 9 ^[1]	T. Denny et al.
RSA-129	129	426	US$100	1994ko Apirilaren 26an ^[3]	Arjen K. Lenstra et al.
RSA-130	130	430	US$14,527^[2]	1996ko Apirilaren 10	Arjen K. Lenstra et al.
RSA-140	140	463	US$17,226	1999ko, Otsailaren 2an	Herman te Riele et al.
RSA-150	150	496		2004eko Apirilaren 16ean	Kazumaro Aoki et al.
RSA-155	155	512	$9,383^[2]	1999ko Abuztuaren 22an	Herman te Riele et al.
RSA-160	160	530		2003ko Apirilaren 1a	Jens Franke et al., Bonneko Unibertsitatea
RSA-170	170	563		2009ko Abenduren 29,	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 Unibertsitatea^[4]
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 26an^[5]	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
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