Competició d'factorización RSA

La Competició d'factorización RSA va ser un desafiu propost pels Laboratoris RSA el 18 de març de 1991 per a fomentar l'investigació en la teoria computacional de números i la dificultat pràctica de la factorización d'número entero grans. Varen publicar una llista de semiprimos (números que tenen exactament dos factors primers) coneguda com els números RSA, en un premi en metàlic per a la factorización en èxit d'alguns d'ells. El més chicotet de tots, un número en 100 sifres decimals conegut com RSA-100 va ser factorizado en pocs dies^{cita requerida}, pero la majoria dels números més grans encara no han segut factorizados i s'espera que permaneixquen aixina durant prou temps. La companyia RSA va cancelar la competició en l'any 2007.

Este desafiu estava dissenyat per a seguir el ritme a l'estat de l'art en la factorización de sancers. Una aplicació important és l'elecció de la llongitut de la clave de l'algoritme de sifrat per mig de clau pública de RSA. Els alvanços en este desafiu deurien ser un indicador de quines llongituts de clau són encara segures i per quant temps. Com els laboratoris RSA són els proveïdors dels productes basats en RSA, el desafiu s'usa com a incentiu a la comunitat acadèmica per a atacar el núcleu de les seues solucions, açò és, per a comprovar la seua fortalea.

Els primers números RSA generats des de RSA-100 fins a RSA-500 varen ser etiquetats d'acort en el seu número de sifres decimals; no obstant, a partir de RSA-576 es conten les sifres en el sistema binario. L'excepció a açò és el RSA-617, que va ser creat abans del canvi del sistema de numeració.

Matemàtiques

Siga $n$ un número RSA producte de dos cosins $p$ i $q$, de manera que

$n=pq$.

El problema és trobar eixos dos cosins, coneixent sol $n$.

Siga $s=p+q$; llavors els valors d'algunes funcions aritmètiques bàsiques són

$d(n)=2$,

$\varphi (n)=(p-1)(q-1)=n+1-s$,

$\sigma (n)=(p+1)(q+1)=n+1+s$.

Els premis i els récorts

La taula següent fa un recorregut per tots els números RSA.

Els números del desafiu en llínees roses són números expressats en base 10, mentres que els de les llínees grogues són números expressats en base 2, i que tenien un premi assignat.

Número RSA	Sifres decimals	Sifres binarias	Premi oferit	Factorizado en	- bgcolor="#FFCBCB"	RSA-100	100	330		abril de 1991	Arjen K. Lenstra
RSA-110	110	364		abril de 1992	Arjen K. Lenstra i M.S. Manasse
RSA-120	120	397		juny de 1993	T. Denny et al.
RSA-129	129	426	$100 USD	abril de 1994	Arjen K. Lenstra et al.
RSA-130	130	430		10 d'abril de 1996	Arjen K. Lenstra et al.
RSA-140	140	463		2 de febrer de 1999	Herman J. J. et Riele et al.
RSA-150	150	496		16 d'abril de 2004	Kazumaro Aoki et al.
RSA-155	155	512		22 d'agost de 1999	Herman J. J. et Riele et al.
RSA-160	160	530		1 d'abril de 2003	Jens Franke et al., Universitat de Bonn
RSA-170	170	563		obert
RSA-576	174	576	$10,000 USD	3 de decembre de 2003	Jens Franke et al., Universitat de Bonn
RSA-180	180	596		obert
RSA-190	190	629		obert
RSA-640	193	640	$20,000 USD	2 de novembre de 2005	Jens Franke et al., Universitat de Bonn
RSA-200	200	663		9 de maig de 2005	Jens Franke et al., Universitat de Bonn
RSA-210	210	696		26 de setembre de 2013	Ryan Propper
RSA-704	212	704	$30,000 USD	obert
RSA-220	220	729		obert
RSA-230	230	762		obert
RSA-232	232	768		obert
RSA-768	232	768	$50,000 USD	12 de decembre de 2009	A six-institution research team led by T. Kleinjung
RSA-240	240	795		2 de decembre de 2019	Fabrice Boudot et al.
RSA-250	250	829		obert
RSA-260	260	862		obert
RSA-270	270	895		obert
RSA-896	270	896	$75,000 USD	obert
RSA-280	280	928		obert
RSA-290	290	962		obert
RSA-300	300	995		obert
RSA-309	309	1024		obert
RSA-1024	309	1024	$100,000 USD	obert
RSA-310	310	1028		obert
RSA-320	320	1061		obert
RSA-330	330	1094		obert
RSA-340	340	1128		obert
RSA-350	350	1161		obert
RSA-360	360	1194		obert
RSA-370	370	1227		obert
RSA-380	380	1261		obert
RSA-390	390	1294		obert
RSA-400	400	1327		obert
RSA-410	410	1360		obert
RSA-420	420	1393		obert
RSA-430	430	1427		obert
RSA-440	440	1460		obert
RSA-450	450	1493		obert
RSA-460	460	1526		obert
RSA-1536	463	1536	$150,000 USD	obert
RSA-470	470	1559		obert
RSA-480	480	1593		obert
RSA-490	490	1626		obert
RSA-500	500	1659		obert
RSA-617	617	2048		obert
RSA-2048	617	2048	$200,000 USD	obert

Vore també

• Problema RSA
• The Magic Words llaure Squeamish Ossifrage, la solució trobada en 1994 a RSA-129, el primer desafiu, propost en 1977