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.

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)

Kriptografia
Zenbakien teoria
Lehiaketak
Matematika sariak