Domanda casuale da SQuAD:

Quando si è scoperto che i numeri primi potevano essere applicati alla creazione di algoritmi di crittografia a chiave pubblica?

Risposta:

gli anni '70

Frasi recuperate:

1. Tuttavia, questa visione si è infranto nel 1970, quando è stato annunciato pubblicamente che i numeri primi potrebbero essere utilizzati come base per la creazione di algoritmi di crittografia a chiave pubblica.
2. I numeri primi sono usati in diverse routine nella tecnologia dell'informazione, come la crittografia a chiave pubblica, che fa uso di proprietà come la difficoltà di scomporre grandi numeri nei loro fattori primi.
3. Algoritmi molto più efficienti della divisione di prova sono stati ideati per testare la primalità di grandi numeri.
4. Diversi algoritmi di crittografia a chiave pubblica, come RSA e lo scambio di chiavi Diffie-Hellman, sono basati su grandi numeri primi (ad esempio, i numeri primi a 512 bit sono spesso usati per RSA e i numeri primi a 1024 bit sono tipici per Diffie-Hellman). .
5. I numeri primi vengono utilizzati anche per tabelle hash e generatori di numeri pseudocasuali.
6. Alcuni di questi numeri primi sono stati trovati utilizzando il calcolo distribuito.
7. Per molto tempo, la teoria dei numeri in generale, e lo studio dei numeri primi in particolare, sono stati visti come l'esempio canonico della matematica pura, senza applicazioni al di fuori dell'interesse personale dello studio dell'argomento, ad eccezione dell'uso dei numeri primi. denti dell'ingranaggio per distribuire uniformemente l'usura.
8. Gli algoritmi deterministici forniscono un modo per dire con certezza se un dato numero è primo o meno.
9. La frase "tutti gli algoritmi possibili" include non solo gli algoritmi conosciuti oggi, ma qualsiasi algoritmo che potrebbe essere scoperto in futuro.
10. Ad esempio, la divisione di prova è un algoritmo deterministico perché, se eseguita correttamente, identificherà sempre un numero primo come primo e un numero composto come composto.
11. Espresso come problema decisionale, è il problema di decidere se l'input ha un fattore minore di k. Non è noto alcun algoritmo di fattorizzazione di interi efficiente e questo fatto costituisce la base di diversi moderni sistemi crittografici, come l'algoritmo RSA.
12. Prima dell'inizio della ricerca vera e propria dedicata esplicitamente alla complessità dei problemi algoritmici, sono state poste numerose basi da parte di vari ricercatori.
13. Questo principio locale-globale sottolinea ancora una volta l'importanza dei numeri primi per la teoria dei numeri.
14. Gli algoritmi probabilistici sono normalmente più veloci, ma non dimostrano completamente che un numero è primo.
15. Tuttavia, l'algoritmo quantistico più noto per questo problema, l'algoritmo di Shor, viene eseguito in tempo polinomiale.
16. Il crivello di Eratostene, attribuito a Eratostene, è un metodo semplice per calcolare i numeri primi, anche se i grandi numeri primi che si trovano oggi con i computer non vengono generati in questo modo.
17. Un problema è considerato intrinsecamente difficile se la sua soluzione richiede risorse significative, qualunque sia l'algoritmo utilizzato.
18. Gli algoritmi che utilizzano bit casuali sono chiamati algoritmi randomizzati.
19. Si ritiene che se un problema può essere risolto da un algoritmo, esiste una macchina di Turing che risolve il problema.
20. I numeri di Carmichael sono sostanzialmente più rari dei numeri primi, quindi questo test può essere utile per scopi pratici.
21. Ad esempio, l'elenco dei numeri primi di Derrick Norman Lehmer fino a 10.006.721, ristampato fino al 1956, iniziava con 1 come primo numero primo.
22. La tesi di Cobham afferma che un problema può essere risolto con una quantità ammissibile di risorse se ammette un algoritmo in tempo polinomiale.
23. Euclide mostrò anche come costruire un numero perfetto da un primo di Mersenne.
24. A partire da gennaio 2016 [aggiornamento], il più grande numero primo noto ha 22.338.618 cifre decimali.
25. Tali domande hanno stimolato lo sviluppo di vari rami della teoria dei numeri, concentrandosi sugli aspetti analitici o algebrici dei numeri.