Fin dai tempi di Euclide, cioè circa dal 300 a.C., gli antichi Greci sapevano che ci sono infiniti numeri primi e che essi sono distribuiti in maniera irregolare tra i numeri naturali. Da allora, molti matematici eminenti, come Fermat, Mersenne, Leibniz, Eulero, Gauss ecc., hanno compilato e analizzato lunghi elenchi di numeri primi, nel tentativo di farsi un'idea della loro distribuzione e per cercare delle formule in grado di produrre, se non tutti, almeno "molti"numeri primi.
Per esempio, un importante risultato fu ottenuto nel 1896 da due matematici francesi, Hadamard e De la Vallie Poussin. Essi dimostrarono il seguente teorema, che era stato congetturato quasi un secolo prima da Gauss: il numero dei primi minori o uguali a n può essere approssimato da n/log n (al crescere di n).
D'altra parte, molti matematici dal '600 in poi, a partire da Mersenne, si de dicarono a studiare i numeri del tipo 2p-1, con p primo. Infatti Fermat aveva dimostrato che, se non sono primi, i numeri di questo tipo hanno fattori tutti della forma 2Kp+1, con k numero naturale. Questo semplifica molto il test di primalità, cioè la verifica se sono primi o meno. In effetti, i più grandi primi trovati finora sono proprio primi di Mersenne, cioè del tipo 2p-1. In particolare lo è l'ultimo, quello trovato lo scorso novembre dal ventenne canadese Michael Cameron: si tratta di 213.466.917-1, un numero con oltre 4 milioni di cifre!
Per esempio, un importante risultato fu ottenuto nel 1896 da due matematici francesi, Hadamard e De la Vallie Poussin. Essi dimostrarono il seguente teorema, che era stato congetturato quasi un secolo prima da Gauss: il numero dei primi minori o uguali a n può essere approssimato da n/log n (al crescere di n).
D'altra parte, molti matematici dal '600 in poi, a partire da Mersenne, si de dicarono a studiare i numeri del tipo 2p-1, con p primo. Infatti Fermat aveva dimostrato che, se non sono primi, i numeri di questo tipo hanno fattori tutti della forma 2Kp+1, con k numero naturale. Questo semplifica molto il test di primalità, cioè la verifica se sono primi o meno. In effetti, i più grandi primi trovati finora sono proprio primi di Mersenne, cioè del tipo 2p-1. In particolare lo è l'ultimo, quello trovato lo scorso novembre dal ventenne canadese Michael Cameron: si tratta di 213.466.917-1, un numero con oltre 4 milioni di cifre!
Tornando alla domanda iniziale, quello che spinge a cercare nuovi numeri primi può essere l'emulazione nei confronti degli illustri matematici del passato, il desiderio di gloria, il piacere di battere un record. Nello stesso tempo, ci possono essere risultati collaterali della ricerca svolta, di interesse indipendente. Dagli anni '50 in poi, i conti necessari a verificare che grandi numeri sono primi sono stati effettuati dalle macchine calcolatrici: i programmi per trovare numeri primi sono stati usati per testare del nuovo hardware, c'è stata quindi un'utilità pratica.
A partire dagli anni '80 (e qui vengo alla seconda domanda), grandi numeri primi sono stati usati per cifrare messaggi segreti con il metodo di crittografia a chiave pubblica detto RSA (dai nomi dei suoi ideatori Rivest, Shamir e Adleman, ricercatori del Massachussetts Institute of Technology).
I metodi di crittografia a chiave pubblica prevedono che, chi deve ricevere l'informazione, renda pubblica la chiave (alcuni numeri) e il metodo per cifrare i messaggi. Egli poi, in base a dei "numerisegreti" in suo possesso è in grado di decifrare i messaggi che gli vengono inviati.
I metodi di crittografia a chiave pubblica prevedono che, chi deve ricevere l'informazione, renda pubblica la chiave (alcuni numeri) e il metodo per cifrare i messaggi. Egli poi, in base a dei "numerisegreti" in suo possesso è in grado di decifrare i messaggi che gli vengono inviati.
Nel metodo RSA:
- i numeri segreti sono due numeri primi p, q e un numero N primo con (p-1)(q-1)
- la chiave pubblica è costituita dal prodotto pq e da un numero M tale che MN-1 sia multiplo di (p-1)(q-1)
- il messaggio da trasmettere è un numero intero positivo x, minore di pq;
- il messaggio cifrato è il numero y, ottenuto come resto della divisione di xM perpq
- per decifrare il messaggio, è sufficiente calcolare il resto della divisione di yN perpq.
- i numeri segreti sono due numeri primi p, q e un numero N primo con (p-1)(q-1)
- la chiave pubblica è costituita dal prodotto pq e da un numero M tale che MN-1 sia multiplo di (p-1)(q-1)
- il messaggio da trasmettere è un numero intero positivo x, minore di pq;
- il messaggio cifrato è il numero y, ottenuto come resto della divisione di xM perpq
- per decifrare il messaggio, è sufficiente calcolare il resto della divisione di yN perpq.
Osserviamo che il messaggio deve essere un numero positivo e minore di pq. Pertanto se si tratta di un messaggio in lettere, bisogna innanzitutto trasformarlo in cifre con un metodo qualunque. Se il numero trovato è troppo grande, lo si spezza in numeri più piccoli da trasmettere separatamente.
La spiegazione del metodo si basa sul seguente teorema, che a sua volta segue da un famoso teorema, noto come piccolo teorema di Fermat.
La spiegazione del metodo si basa sul seguente teorema, che a sua volta segue da un famoso teorema, noto come piccolo teorema di Fermat.
Teorema Se 0≤x(xM)N è congruo a x modulo pq.
Nella pratica, bisogna scegliere p e q primi molto grandi, in modo che sia impossibile fattorizzare pq in tempo ragionevole. Il metodo infatti si basa sull'assunzione che sia estremamente difficile risalire a p e q conoscendo il loro prodotto.
Se chi intercettasse un messaggio fosse in grado di fattorizzare pq, di conseguenza conoscerebbe anche (p-1)(q-1), e per trovare N gli sarebbe sufficiente risolvere l'equazione
Se chi intercettasse un messaggio fosse in grado di fattorizzare pq, di conseguenza conoscerebbe anche (p-1)(q-1), e per trovare N gli sarebbe sufficiente risolvere l'equazione
MN = 1 mod (p-1)(q-1),
con M e (p-1)(q-1) primi tra loro, entrerebbe così facilmente in possesso di tutte le informazioni necessarie a decifrare il messaggio.
Il rapido sviluppo di nuove tecniche per la fattorizzazione dei numeri composti sta rendendo problematico l'uso del metodo RSA. Si è infatti costretti a usare numerip,q sempre più grandi, cosa che rende molto lungo il calcolo di y e di yN mod pq. Ci si sta orientando dunque a tornare a metodi crittografici classici, trasmettendo col metodo RSA soltanto la chiave.
Il rapido sviluppo di nuove tecniche per la fattorizzazione dei numeri composti sta rendendo problematico l'uso del metodo RSA. Si è infatti costretti a usare numerip,q sempre più grandi, cosa che rende molto lungo il calcolo di y e di yN mod pq. Ci si sta orientando dunque a tornare a metodi crittografici classici, trasmettendo col metodo RSA soltanto la chiave.
Per saperne di più, consiglio i libri:
K. Devlin, Dove va la matematica?, Boringhieri
D. M. Davis, The nature and power of mathematics, Princeton University Press
S. Singh, Codici e Segreti, Rizzoli
D. M. Davis, The nature and power of mathematics, Princeton University Press
S. Singh, Codici e Segreti, Rizzoli
e i siti web:
Emilia MezzettiDipartimento di Matematica e Informatica, Università di Trieste
Nessun commento:
Posta un commento