Algebra 1/Numeri/Numeri Naturali: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Riga 498:
 
=== Numeri primi e crittografia ===
 
Il problema legato alla scomposizione in fattori primi è di notevole interesse per i matematici, poiché non è ancora stato individuato un meccanismo che permette di stabilire se un numero sia primo o meno <ref>si tratta della dimostrazione dell’ipotesi di Riemann, uno dei 7 ''Millennium problems'' elencati il 24 maggio 2000, ovvero questioni matematiche ad oggi (2014) ancora non dimostrate (tranne una). Vista l’enorme difficoltà nel riuscire nell’intento, il Clay Mathematics Institute ha messo in palio un milione di dollari per la dimostrazione di ognuna di esse</ref>, se non quello di provare a dividerlo per tutti i numeri minori o uguali alla sua radice quadrata, procedura che diventa sempre più lunga man mano che le cifre che compongono il numero da verificare aumentano. Per questo motivo l’utilizzo di valori che siano il prodotto di numeri primi con un numero elevato di cifre è ciò che sta alla base della moderna crittografia, ovvero dei sistemi per la cifratura dei messaggi.
 
Consideriamo un semplice esempio che può chiarire come funziona il meccanismo di base per inviare messaggi segreti.
 
Alice deve inviare la sua password, la parola “BACI”, a suo fratello Bruno. Alice trasforma la parola in numeri secondo la semplice regola <math>A=1,\, B=2,\, C=3,\, I=9</math> (assegnando ad ogni lettera il numero cardinale corrispondente alla sua posizione nell’alfabeto). Il messaggio diventa così <math>{2\,139}</math>. Alice moltiplica questo numero per un numero primo “segreto” (che conosce solo lei) <math>{26\,417}</math> e ottiene <math>{2\,139} \cdot {26\,417}={56\,505\,963}</math> e invia quest’ultimo numero a Bruno. Chiunque intercetti questo numero non è in grado di individuare la password in chiaro.
 
Quando Bruno riceve il numero <math>{56\,505\,963}</math> lo moltiplica per un suo numero primo “segreto” (che conosce solo lui) <math>{43\,969}</math> ottenendo <math>{5\,650\,593} \cdot {43\,969}={2\,484\,510\,687\,147}</math> e lo invia nuovamente ad Alice.
 
Quando Alice riceve il numero lo divide per il suo numero primo <math>{2\,484\,510\,687\,147} : {26\,417} = {94\,049\,691}</math> e quindi lo rispedisce a Bruno, A questo punto Bruno divide il numero ricevuto per il suo numero primo segreto ottenendo <math>{94\,049\,691} : {43\,969} = {2\,139}</math>. Conoscendo il meccanismo di codifica (relazione tra i numeri e le lettere dell’alfabeto <math>2=B,\, 1=A,\, 3=C,\, 9=I</math>) Bruno può dunque ricostruire la password “BACI”.
 
In realtà, i sistemi per lo scambio di messaggi cifrati oggi utilizzati per mezzo dei computer si basano su meccanismi leggermente differenti che evitano il doppio invio di messaggi tra Alice e Bruno. I meccanismi sono essenzialmente due: il primo è detto ''a chiave simmetrica'', in cui sia Alice che Bruno condividono il numero segreto con il quale viene cifrato il messaggio e quindi entrambi possono codificarlo e decodificarlo autonomamente; il secondo, un po’ più complesso ma che dà le stesse garanzie del doppio invio di messaggi (nessuna condivisione del numero segreto tra gli interlocutori), viene chiamato ''a chiave asimmetrica'' e si basa sull’utilizzo di un numero segreto ed un numero pubblico da condividere con l’interlocutore.
 
Va comunque sottolineato il fatto che la robustezza del meccanismo di cifratura sta nella difficoltà intrinseca della fattorizzazione di numeri molto grandi. Ciò non significa che i messaggi rimarranno segreti per sempre: prima o poi saranno decifrati visto che la velocità di calcolo dei computer è sempre in aumento. Per cercare di rendere il processo di decifratura più arduo si possono scegliere chiavi di cifratura composte da numeri primi sempre più grandi.
 
== Massimo Comune Divisore e minimo comune multiplo ==