RSA Factoring Challenge

Da Wikipedia, l'enciclopedia libera.

Il RSA Factoring Challenge è una sfida proposta da RSA Laboratories dal 18 marzo 1991 per incoraggiare la ricerca nel campo della teoria dei numeri computazionale e nella difficile fattorizzazione di grandi numeri naturali. Essi pubblicarono una lista di semiprimi (numeri che hanno esattamente due fattori primi) conosciuti come numeri RSA, con un premio in denaro per chi fosse riuscito a fattorizzarli. Il più piccolo di questi, un numero con 100 cifre decimali è chiamato RSA-100, fu fattorizzato in pochi giorni, ma molti dei numeri più grossi non sono stati ancora fattorizzati e ci si aspetta che rimarranno tali ancora per un tempo relativamente lungo.

Questa sfida ha lo scopo di sondare lo "stato dell'arte" nella fattorizzazione di interi. Una primaria applicazione è la scelta della lunghezza della chiave per l'algoritmo RSA di crittografia a chiave pubblica.

I primi numeri RSA generati, dal RSA-100 al RSA-500, furono chiamati in accordo con il numero di cifre decimali; tuttavia, in seguito, dal numero RSA-576, si contò il numero di cifre binarie. Un'eccezione è per il numero RSA-617, che fu creato prima del cambiamento nel sistema di numerazione.

[modifica] Matematica

Sia n un numero RSA. Esistono e sono unici due numeri primi p e q tali che

n = p q .

Il problema è trovare questi due numeri primi, conoscendo solo n.

Sia s = $p + q$ ; allora il valore di alcune funzioni aritmetiche di base

d (n) = 2

φ(n) = (p - 1)(q - 1) = n + 1 - s

σ(n) = (p + 1)(q + 1) = n + 1 + s .

[modifica] Premi e annotazioni

La seguente tabella fornisce una visione dei numeri RSA.

Il numero con cui cono catalogati i numeri RSA su sfondo rosa è espresso in base 10, mentre su sfondo giallo è espresso in base 2.

Numero RSA	Cifre decimali	Cifre binarie	Premio offerto	Data fattorizzazione	Fattorizzato da
RSA-100	100	330		Aprile 1991	Arjen K. Lenstra
RSA-110	110	364		Aprile 1992	Arjen K. Lenstra e M.S. Manasse
RSA-120	120	397		Giugno 1993	T. Denny et al.
RSA-129	129	426	$100 USD	Aprile 1994	Arjen K. Lenstra et al.
RSA-130	130	430		10 aprile 1996	Arjen K. Lenstra et al.
RSA-140	140	463		2 febbraio 1999	Herman J. J. te Riele et al.
RSA-150^[1]	150	496		16 aprile 2004	Kazumaro Aoki et al.
RSA-155	155	512		22 agosto 1999	Herman J. J. te Riele et al.
RSA-160	160	530		1 aprile 2003	Jens Franke et al., University of Bonn
RSA-170	170	563		aperto
RSA-576	174	576	$10,000 USD	3 dicembre, 2003	Jens Franke et al., University of Bonn
RSA-180	180	596		aperto
RSA-190	190	629		aperto
RSA-640	193	640	$20,000 USD	Novembre, 2005	Jens Franke et al., University of Bonn
RSA-200	200	663		9 maggio 2005	Jens Franke et al., University of Bonn
RSA-210	210	696		aperto
RSA-704	212	704	$30,000 USD	aperto
RSA-220	220	729		aperto
RSA-230	230	762		aperto
RSA-232	232	768		aperto
RSA-768	232	768	$50,000 USD	aperto
RSA-240	240	795		aperto
RSA-250	250	829		aperto
RSA-260	260	862		aperto
RSA-270	270	895		aperto
RSA-896	270	896	$75,000 USD	aperto
RSA-280	280	928		aperto
RSA-290	290	962		aperto
RSA-300	300	995		aperto
RSA-309	309	1024		aperto
RSA-1024	309	1024	$100,000 USD	aperto
RSA-310	310	1028		aperto
RSA-320	320	1061		aperto
RSA-330	330	1094		aperto
RSA-340	340	1128		aperto
RSA-350	350	1161		aperto
RSA-360	360	1194		aperto
RSA-370	370	1227		aperto
RSA-380	380	1261		aperto
RSA-390	390	1294		aperto
RSA-400	400	1327		aperto
RSA-410	410	1360		aperto
RSA-420	420	1393		aperto
RSA-430	430	1427		aperto
RSA-440	440	1460		aperto
RSA-450	450	1493		aperto
RSA-460	460	1526		aperto
RSA-1536	463	1536	$150,000 USD	aperto
RSA-470	470	1559		aperto
RSA-480	480	1593		aperto
RSA-490	490	1626		aperto
RSA-500	500	1659		aperto
RSA-617	617	2048		aperto
RSA-2048	617	2048	$200,000 USD	aperto