È possibile generare ogni possibile combinazione di una stringa alfanumica di 32 caratteri? Se sì, quanto tempo impiegherebbe nei computer veloci di oggi?
Il mio docente universitario ha detto che è impossibile, e ho pensato che "nulla è impossibile".
Qualche idea su quanto tempo ci vorrà e come sarebbe stata fatta? Al momento utilizziamo Java. Mi piacerebbe pensare di poterlo dimostrare che torto.
Si riduce alla matematica, anche se prendi valori piuttosto folli.
Diciamo che hai un'istruzione che può generare una combinazione di 32 caratteri in un ciclo. Inoltre, non stai memorizzando queste combinazioni quindi non c'è praticamente alcun accesso alla memoria. Supponiamo infine che la velocità di clock effettiva per queste istruzioni sia di 2,0 petahertz (da dieci a quindici cicli al secondo), che non esiste ancora al di fuori dei supercomputer più veloci del pianeta.
Il numero di 32 combinazioni di caratteri alfanumeriche con ripetizione è 36 alla 32a potenza. Quindi, il 10 al 32 ° potere è un limite inferiore molto più piccolo su questo valore. Per calcolare questo gruppo più piccolo, occorrono dai 10 ai 17 secondi (combinazioni / velocità di clock). Ci sono circa 32 milioni di secondi in un anno, quindi per questo esempio impiegheremo 100 milioni di secondi in 3 anni per semplificare i calcoli matematici.
Quindi questo ci lascia da 10 a 17 secondi divisi per 10 e 8 secondi per 3 anni. Ciò significa che ci vorranno più di 3 miliardi di anni per completare questo calcolo. Controlla che contro il tempo stimato che ci rimane prima che il nostro sole diventi un gigante rosso, sono solo 5 miliardi di anni ...
Suggerirei di provare a generare le prime 10000 combinazioni e a misurare quanto tempo impiega Java.
Quindi, come stima approssimativa, calcolare il tempo necessario per combinazione nella dimensione del campione e più volte il numero totale di combinazioni possibili. (Forse anche fare la matematica prima di determinare quante combinazioni ci sono perché questo è il vero problema).
Questo tipo di domanda mostra un ottimo modo per esercitarti con stime e ordini di grandezza . In tutti i campi scientifici e tecnici, questo è un grande vantaggio. In effetti, è la cosa numero uno che mi aspetto dalle persone che assumo: essere in grado di fare ipotesi plausibili quando non ci sono dati disponibili.
Quindi, iniziamo subito:
Non è necessario generare ogni stringa possibile - esiste già. Se stai cercando una stringa particolare, non hai bisogno di cercare. Esiste. Se vuoi memorizzarlo, è già archiviato - ci vogliono 0 byte per memorizzare e 0 volte per recuperare.
In altre parole, il risultato esiste già ed è memorizzato nella trama della realtà, quindi generare il risultato è in realtà l'operazione più rapida possibile.
È un po 'come chiedere a qualcuno di scrivere un algoritmo di ordinamento che ordina tutti gli interi da 1 a 1000, dato che ognuno è unico. Non è necessario ordinare affatto.
Dato che ci sono 62 caratteri alfanumerici , la quantità di combinazioni possibili è uguale a 62 ^ 32 = 2.27e 57 . Conosciuto anche come .. enorme!
Curiosità: la memorizzazione di questo con 8 bit per carattere occuperebbe 1792810956021776957992730108.0124 Geopbyte
Come afferma jzd, prova a confrontare il tempo necessario per generare una certa quantità di essi. Da questo puoi calcolare un tempo medio per combinazione, moltiplicarlo con la quantità di combinazioni possibili e avrai il tempo richiesto.
Ovviamente è possibile. O il tuo docente suggerisce che c'è una combinazione di lettere / numeri che non può essere rappresentata in una stringa di 32 caratteri?
è Fattibile ... ora è una domanda completamente diversa. Se tu fossi in grado di sfruttare la maggior parte delle macchine su Internet, probabilmente potresti farlo in un arco temporale abbastanza piccolo da rendere il risultato finale ancora pertinente.
Se pensiamo fuori dagli schemi per un po ', questo tipo di esplosione combinatoria è ciò a cui i computer quantistici sono bravi. Se hai 64 simboli (6 bit) e una lunghezza di 32, avrai bisogno di un computer quantico 6 * 32 = 192 bit per risolverlo "istantaneamente", a seconda di cosa vuoi realmente fare con le stringhe - stai cercando per uno con un hash che corrisponde a un determinato valore di hash?
Per inciso, a partire da pochi giorni fa, è possibile ordinare un computer quantistico a 128 bit da D-wave (molto conteso se si tratta di un calcolo quantistico, comunque). Questo non è ancora abbastanza, dal momento che mancano 64 bit, il che significa che avresti bisogno di eseguire il tuo algoritmo 2 ** 64 volte, che è ancora troppo lungo.
192 bit probabilmente arriveranno prima o poi comunque. Allora sarai in grado di mostrarlo;)
Leggi altre domande sui tag java php algorithms cryptography