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.
Indice |
[modifica] Matematica
Sia n un numero RSA. Esistono e sono unici due numeri primi p e q tali che
- n = pq.
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 | |
- ^ RSA-150 fu ritirato dalla sfida originale dall'RSA Security, ma è stato comunque fattorizzato.
[modifica] Voci correlate
- RSA Secret-Key Challenge
