I Numeri Primi E Internet

Cari lettori, (ragazzi per voi questo post non è facile da capire,...però se volete leggerlo! Non si sa mai...)

Nel corso della ventesima edizione del Carnevale della Matematica, ospitato da questo blog, c'è stata una marea di contributi interessanti. Di questi, riporto integralmente il contributo di Mauretto, che ha dato il consenso.

Grazie, Mauro!

**********

I numeri primi e Internet

Ai matematici e filosofi greci che tanto tempo fa iniziarono a studiare i numeri primi e le loro proprietà, certo non poteva passare per la mente che, oltre duemila anni dopo, quei loro studi (con i contributi di tanti altri matematici che seguirono) sarebbero stati utilizzati per rendere più sicure le transazioni commerciali ai tempi nostri... Eppure è così, e vediamo come, attraverso questa carrellata sulla storia del numero primo...


1. I numeri primi per gli antichi greci

In principio era l’1. Da esso, aggiungendo un’unità per volta, è possibile creare tutti i numeri interi (che d’ora in poi chiamerò anche naturali) che si vogliono, basta averne il tempo e la voglia... Ma non tutti i naturali, pur avendo lo stesso progenitore, per così dire, sono uguali; per esempio esistono i pari e i dispari, i perfetti, difettivi e perfettivi ecc. Una delle caratterizzazioni principali dei naturali è quella che li suddivide in primi e composti. Vengono detti primi tutti quelli che sono divisibili soltanto per se stessi e per 1, composti tutti gli altri (l’1, di per sé, è un caso particolare: rientrerebbe nella definizione appena data, ma i matematici non lo considerano primo, per ragioni logiche, ma che qui adesso non sto a specificare).

Già Euclide, vissuto nel IV-III secolo p.e.v., si era posto il problema di quanti fossero i numeri primi, ovvero, per meglio dire, se essi fossero in numero limitato o no. Dimostrò con un procedimento semplicissimo (anche se coinvolge un tipo di ragionamento, quello per assurdo, che risulta abbastanza ostico a chi non è addentro in questioni di matematica o di logica) che essi sono in numero infinito, e che dunque non esiste un numero primo più grande di tutti. Dimostrò inoltre che ogni numero composto ammette una e una sola scomposizione in fattori primi (a meno dell'ordine dei fattori, naturalmente).

Eratostene, altro matematico greco (vissuto un secolo circa dopo Euclide) si pose il problema di determinare quali fossero i numeri primi e quali quelli composti. Inventò, a tale scopo un sistema ingegnoso; il procedimento è il seguente: si supponga di voler trovare tutti i numeri primi fino a 1000; allora, scriviamo tutti questi numeri a partire da 2 fino a 1000 in un elenco; poi, partiamo da 2 e cominciamo a cancellare tutti i multipli di 2 (il 2 escluso); poi cominciamo da 3 (il primo che ancora non è stato cancellato) e cancelliamo (setacciamo) tutti i multipli di 3; e così via, partendo dal primo numero che non è stato cancellato, cancelliamo tutti i suoi multipli (escluso lui stesso). Proseguiamo così fino ad arrivare all’ultimo numero della nostra lista, 1000. I numeri che restano sono i numeri primi non maggiori di 1000. È come se si utilizzassero dei setacci a maglie via via più larghe: il primo lascia passare soltanto i numeri non multipli di 2, il secondo soltanto i non multipli di 3, e così via. Il procedimento viene effettivamente chiamato “crivello (setaccio) di Eratostene”.

Dopo i greci, c’è stato un lungo periodo di stasi, nella ricerca sui numeri primi. Per trovare un altro matematico che se ne sia occupato, bisogna arrivare addirittura al XVII secolo, al francese Pierre de Fermat e al suo coevo e conterraneo Marin Mersenne.

I due (oltre a numerosi altri argomenti) si occuparono principalmente di trovare una formula, un procedimento che fornisse numeri primi, dato che il crivello di Eratostene era sì efficace, ma pochissimo efficiente. Fermat arrivò alla formula

Egli credeva che questa formula fornisse soltanto numeri primi, mentre già fallisce per n = 5, dando un numero composto. D’altronde non aveva certo a disposizione le moderne calcolatrici, e a mano era praticamente impossibile controllare se 4 294 967 295 (il valore dell’espressione sopra con n = 5) fosse primo o composto...

Mersenne, invece, pervenne all’ancor più efficace (ed efficiente)
 
che fornisce moltissimi numeri primi. Il più grande che sia stato a oggi trovato è 242 643 801 - 1, un numero di 12 837 064 cifre!

Ma il contributo più importante (almeno dal punto di vista dell’argomento di questo post) che Fermat diede alla teoria dei numeri primi è quello che oggi viene chiamato “piccolo teorema di Fermat” (per distinguerlo da quello più famoso, del quale ho già parlato in questo post). Tale teorema stabilisce che
 

che si legge “a alla p è congruo ad a modulo p” affermando con ciò che, prendendo un qualsiasi numero a, elevandolo a una potenza prima p, ed eseguendo infine una divisione per lo stesso p, si ottiene un resto uguale al numero originario. Questo teorema costituisce la base della moderna tecnica crittografica, della quale parlerò oltre.

Toccò poi a Eulero, un matematico svizzero, che, oltre a confutare o dimostrare alcune delle affermazioni fatte da Fermat sui numeri primi, si imbatté a un certo punto dei suoi studi nel calcolo della somma infinita (detta anche serie armonica)
 
e dimostrò che divergeva, cioè che la somma era infinita; ma, generalizzando, decise di studiare cosa avveniva se ogni termine veniva elevato al quadrato:
 
oppure, in genere, a un esponente maggiore di 1:
 
con n > 1. Ebbene, Eulero dimostrò che, nel caso in cui l'esponente fosse maggiore di 1, la serie improvvisamente convergeva.

Una serie di queste, in particolare, destò in Eulero e negli altri matematici particolare stupore; era quella in cui l’esponente valeva 2. Lo svizzero, dopo numerosi calcoli, dimostrò che
 un’espressione che legava la somma degli inversi di tutti i quadrati al rapporto tra una circonferenza e il suo diametro… una scoperta quasi mistica!

Cosa ancora più importante, però, dimostrò che la serie armonica poteva essere espressa in termini di prodotti di fattori contenenti in qualche modo i numeri primi, cioè che:
 
(dove al denominatore, nel membro di destra, compaiono tutti i numeri primi) ovvero, scritto in termini matematici più compatti,
 
Dove quel simbolo strano (una pi greca maiuscola) che vedete nel membro di destra si chiama produttorio ed è l’analogo della sommatoria (che è il simbolo a sinistra, una sigma maiuscola), ma per i prodotti.

E poi… poi arrivò Riemann, e fu tutta un’altra musica…

2. I numeri primi ai tempi nostri

Bernhard Riemann era un matematico tedesco che insegnava all’Università di Gottinga; verso la metà del XIX secolo, si occupava soprattutto di geometria non euclidea. Quasi improvvisamente nell’ambiente matematico iniziarono a circolare dei tipi di numeri, introdotti dal francese Cauchy, un po’ “strani”, che servivano a risolvere alcune equazioni polinomiali (ricordate questo post su Galois, vero? ); erano i numeri complessi, cioè i numeri della forma a + b • i, dove a e b sono numeri reali, mentre i = √(-1). Riemann ne restò talmente affascinato che iniziò a studiare il comportamento delle funzioni “normali” quando le variabili, invece che essere numeri reali, erano numeri complessi.

Tra l’altro, cominciò a studiare il comportamento di questa funzione:
 

(quel simbolo strano che vedete a sinistra è una zeta greca maiuscola, che noi matematici normalmente leggiamo “zita” per distinguerla dalla zeta dell’alfabeto latino, meno che quando la leggiamo nel caso di questa funzione, dove ridiventa “zeta”, ed esattamente “zeta di Riemann”… siamo un po’ pazzi noi matematici, vero? ). Comunque, come avrete notato, è proprio la funzione studiata da Eulero, soltanto che l’esponente dei naturali, invece di essere un numero reale, è un numero complesso (sì, coi numeri complessi si possono eseguire esattamente le stesse operazioni che sui numeri reali, a parte qualche minima eccezione…).

Insomma, Riemann iniziò a studiare questa funzione e si accorse di parecchie particolarità; innanzitutto che essa assumeva il valore 0 per certi determinati valori della variabile complessa s, e precisamente i punti 2, 4, 6 ecc. Questa caratteristica era abbastanza evidente a occhio, per così dire, e Riemann chiamò questi gli “zeri banali” della funzione zeta che da lui prese il nome (in matematica gli “zeri” di una funzione sono i valori della variabile per i quali essa assume valore 0). Molto più interessante si rivelò invece la ricerca degli “zeri non banali”.

La funzione zeta di Riemann è in effetti abbastanza sfuggente all’analisi, e soltanto dopo molte pene il tedesco si accorse che gli zeri non banali sembravano addensarsi su una particolare retta, detta poi “retta critica”, quella di ascissa ½, sicché le soluzioni sembravano essere tutte della forma ½ + b • i.

Ma torniamo ora, per un attimo, ai numeri primi. Circa mezzo secolo prima di Riemann, un altro matematico tedesco suo predecessore all’università di Gottinga, Carl Friedrich Gauss, aveva investigato sul “numero” dei numeri primi, cioè su quanti ce ne fossero in un intervallo dato. Egli, visto che fino a quel momento non si era riusciti a trovare nessuna formula che restituisse tutti e soli i numeri primi, passò all’analisi della frequenza dei numeri primi all’interno dei naturali ovvero (concetto più o meno analogo) alla probabilità che dato un numero qualsiasi, questo fosse primo.

Esaminando le tavole dei numeri primi che circolavano, e calcolandone diverse migliaia lui stesso (scrisse a un suo corrispondente: “ogni volta che ho un attimo di tempo libero mi dedico alla ricerca di numeri primi”), stimò, in prima battuta, che il numero dei primi non superiori al numero x, da lui indicato con il simbolo π(x), fosse circa uguale a
 

dove ln x rappresenta il logaritmo naturale (in base e) di x. Questa congettura di Gauss venne migliorata dal matematico francese Legendre, che approssimò la frequenza dei numeri primi con la formula
 
che, in effetti, era più aderente alla quantità richiesta. Permettetemi però questa digressione: quella di Legendre è una formula decisamente più brutta (nel senso di “pesante”), pur se migliore, di quella di Gauss, e io sono convinto che la Natura (intesa in senso spinoziano) abbia la facoltà di scegliere, tra due possibili soluzioni alle sue leggi, quella più bella, elegante e comprensibile…

Tant’è, infatti, che lo stesso Gauss trovò un’approssimazione migliore di quella di Legendre e, addirittura, infinitamente più elegante! Questa:
 
(dove il simbolo ~ vuol dire “circa uguale a”).

Anche Riemann si era dedicato allo studio della frequenza dei numeri primi e, tentando di migliorare la stima effettuata da Gauss, arrivò alla stupefacente connessione tra la frequenza dei numeri primi e la funzione zeta, nel senso che aggiungendo o togliendo alla stima di Gauss una quantità determinata in base agli zeri della funzione zeta, quel segno di “quasi uguale” diventava un “uguale” vero e proprio!

Ma… e qui sorge un grande “ma”, un immenso “ma”, starei per dire: quello che ho detto nel paragrafo precedente è vero “se e soltanto se” gli zeri non banali della funzione zeta stanno tutti su quella famosa retta “critica” di ascissa ½. Dal momento in cui Riemann enunciò questa congettura (quella sugli zeri), decine, ma che dico, centinaia di matematici hanno tentato di dimostrarla, eppure nessuno c’è riuscito.

Addirittura, nel 1900, un altro matematico tedesco, David Hilbert, il più geniale dell’epoca, inserì l’ipotesi di Riemann tra i “problemi del secolo”, quelli che nel corso del novecento, appunto, avrebbero dovuto essere risolti; ebbene, è passato un secolo e rotti, e l’ipotesi di Riemann è ancora lì, perenne “teorema di Fermat”, a sfidare i matematici. E non è che nel frattempo le cose non siano andate avanti: ormai sono stati calcolati decine di miliardi di zeri non banali della funzione zeta, e tutti giacciono sulla retta di ascissa ½; è stato dimostrato che oltre il 40% degli zeri è su quella retta; è stato dimostrato che gli zeri su quella retta sono infiniti, ma (sapete bene come vanno le cose con i “numeri infiniti”, se avete letto questo mio racconto) ancora nessuna dimostrazione può garantire che qualche zero sperduto non si trovi al di fuori di essa…

3. Numeri primi e crittografia

Compiuto questo excursus nella storia dei numeri primi, veniamo ora al cuore di quella che è la seconda parte del titolo di questi post: Internet, e più precisamente la sicurezza dei dati nella rete.

Non farò qui la storia della crittografia, ma dimostrerò semplicemente perché la trasmissione dei dati in Internet può (ancora?) considerarsi sicura.

Il metodo attraverso il quale si realizza tale sicurezza si chiama RSA (dalle iniziali dei cognomi dei suoi inventori: Ron Rivest, Adi Shamir e Leonard Adleman). È un sistema “a chiave pubblica”, nel senso che lo strumento per codificare un qualsiasi messaggio può essere noto a tutti, mentre è “privato”, ovvero nascosto, lo strumento per decodificarlo: quest’ultimo è noto soltanto al destinatario del messaggio stesso. Vediamo in pratica come funziona, con un esempio costruito appositamente. Supponiamo che ci siano due persone, Alice e Bruna, e che la seconda debba spedire un messaggio cifrato alla prima; per comodità di calcolo, farò semplicemente consistere tale messaggio nel numero “7”.

Prima di tutto, Alice costruisce la “chiave pubblica”; la crea prendendo due numeri primi ed eseguendone il prodotto; nella realtà i numeri scelti sono molto grandi, ma noi, sempre per comodità di calcolo, supponiamo che siano 5 e 11: la prima parte della chiave pubblica è allora 55 e questo numero viene comunicato a Bruna, senza alcun timore che qualcun altro lo possa scoprire, perché, come vedremo è, con quasi assoluta certezza, inutilizzabile. Secondariamente, Alice esegue il prodotto (5 – 1) • (11 – 1) = 40; questo numero costituisce la sua “chiave privata” e viene tenuto segreto perché è quello che serve a decodificare il messaggio.

Dopodiché Alice cerca il minimo naturale che non abbia fattori comuni con la chiave privata (40); in questo caso è il numero 3: questo costituisce la seconda parte della chiave pubblica e anch’esso viene comunicato a Bruna.

Infine Alice calcola il numero inverso di 3 (la seconda parte della chiave pubblica) nell'aritmetica modulare di ordine 40 (la prima parte della chiave privata), cioè il più piccolo numero x per il quale vale 3 • x ≡ 1 (mod. 40) , vale a dire il minimo numero che, moltiplicato per 3, dia resto 1 quando diviso per 40; in questo caso x = 27, e questa sarà la seconda parte della chiave privata.

A questo punto Bruna conosce la chiave pubblica (divisa in due parti) e la utilizza per eseguire il seguente calcolo: 73 mod. 55, cioè eleva 7 alla terza potenza e calcola il resto della divisione del risultato per 55, ottenendo 13, che costituisce il “messaggio cifrato” da inviare ad Alice.

Questa, una volta ricevuto il numero 13, esegue il calcolo 1327 mod. 55, cioè eleva 13 alla ventisettesima potenza e calcola il resto della divisione per 55 (in realtà non c’è proprio bisogno di elevare a quella potenza enorme, c’è un sistema più rapido, ma tralascio volutamente alcuni tecnicismi). Il risultato è 7, cioè il messaggio originario di Bruna!

Tutto questo procedimento, che mi ha richiesto quasi una pagina per l’esposizione, e a voi qualche minuto, più o meno, per la lettura, in realtà viene eseguito in pochi millesimi di secondo da un qualsiasi calcolatore, anche di media potenza.

E allora, per concludere, vediamo la caratteristica fondamentale del sistema RSA reale, quella che lo rende praticamente inespugnabile. Nel mio esempio ho volutamente utilizzato numeri piccoli, ma le aziende che commerciano su Internet (nonché i servizi segreti, grandi utilizzatori di crittografia!) utilizzano attualmente “chiavi pubbliche” che sono il prodotto di due numeri primi di 160-320 cifre (e i servizi segreti utilizzano, quasi sicuramente, numeri primi di 600 cifre e oltre…); dunque, se è facile, dato il numero 55 del mio esempio, scoprire che i suoi fattori primi sono 5 e 11, per i numeri “reali” di centinaia di cifre tale compito è decisamente al di là delle attuali possibilità, anche con i supercalcolatori che ci sono oggi in circolazione; e senza “fattorizzazione” non si può in alcun modo risalire alla chiave privata e al messaggio non cifrato.

Quest’ultima considerazione vale però finché perdura lo stato di relativa incertezza riguardante l’ipotesi di Riemann; nel momento in cui venisse scoperto uno “zero non banale” al di fuori della “retta critica” (ipotesi altamente improbabile) oppure quando (più probabilmente, in un futuro forse non troppo lontano) verrà dimostrata matematicamente la validità dell’ipotesi, il problema della fattorizzazione di numeri con parecchie centinaia di cifre sarà enormemente più facile e bisognerà trovare un altro sistema per codificare i messaggi che debbono rimanere segreti. Ma, nel frattempo, non è che i crittografi (coloro che si occupano di tecniche di occultamento di messaggi) stiano con le mani in mano: altri metodi di crittazione sono in fase di studio avanzata, e sono basati su “biliardi ellittici”, “tamburi quantistici”, “calcolatori cellulari” e altri aggeggi simili, direttamente dai romanzi di fantascienza!

4. Considerazioni finali (con una sorpresina)

Un’ultima annotazione, che non so quanto sia originale (anche se lo spero vivamente); mentre stavo scrivendo questo post, mi sono messo un po’ a giocherellare con il crivello di Eratostene (quello menzionato all’inizio); sorseggiavo l’ennesimo caffè della giornata (dato che sono un pedissequo sostenitore dell’affermazione del matematico ungherese Paul Erdős, secondo il quale “un matematico è una macchina semplice che trasforma caffè in teoremi…”), quando ho scoperto una cosa che non mi pare di aver trovato altrove nella letteratura da me consultata; è una sciocchezzuola, ma ve la propongo così come m’è venuta in mente.

Dunque: dopo secoli di studio sui numeri primi non si è arrivati a una formula che restituisca soltanto numeri primi; esistono formule complicatissime che dànno numeri primi: quelle di Fermat e Mersenne, per esempio, ma non solo; ben quattro matematici (tali Jones, Sato, Wada e Wiens, sconosciuti, credo, per altro che non sia il motivo che vi vado a esporre…) nel 1976 si sono messi insieme per creare questo mostro di espressione
 
in 26 variabili (le lettere a, b, …, z) e di grado 25! Sostituendo alle lettere numeri naturali qualsiasi, se il risultato è un numero positivo, allora è anche un numero primo (ed esistono valori delle variabili che ritornano ogni primo possibile); peccato che il più delle volte quell’espressione ritorni un numero negativo…

A parte le mostruosità, dicevo che non sembra esistere un sistema per sapere a priori, dato un numero primo, quale sarà il successivo. A me sembra, tuttavia, di aver trovato un metodo a posteriori, che consiste in questo: esaminiamo con attenzione il metodo del crivello di Eratostene (amo molto, casomai non si fosse capito, questo ritorno alle origini, alla matematica “semplice”…).

Se osserviamo attentamente cosa succede quando cancelliamo i multipli di ogni numero, notiamo questo fatto: il primo a venire cancellato è il quadrato del numero stesso (il 4 è il primo multiplo del 2, il 9 è il primo multiplo del 3 − dato che il 6 è già stato cancellato come multiplo di 2 −, il 25 è il primo multiplo del 5 e così via).

Il fenomeno particolare si nota quando si va a cancellare il secondo multiplo: per il 2 il secondo multiplo è il 6 (= 2 • 3), per il 3 è il 15 (= 3 • 5), per il 5 è il 35 (= 5 • 7), per il 7 è il 77 (= 7 • 11)… Il secondo a essere sottoposto a cancellazione è un numero che, diviso per quello da cui ha origine l’eliminazione, restituisce il numero primo successivo!

È come se la Natura (intesa sempre nel senso spinoziano del termine), fornendoci i numeri primi e celandoci contemporaneamente la loro distribuzione, avesse nascosto dentro ognuno una traccia che porta al successivo; come se, consigliata magari da Charles Perrault, ci avesse detto: “Non ti dico come sono distribuiti i numeri primi, ma, come Pollicino, briciola dopo briciola, da ogni numero primo puoi risalire al successivo!” o ancora come se, consigliata da un botanico quale Lamarck, ci fornisse, insieme con ogni numero primo, il seme dal quale far nascere il successivo, o ancora come se, su suggerimento di un grande von Karajan, ogni numero primo desse il “la” a un altro numero primo, a un altro strumento di quell’orchestra infinita; dato che, come ebbe ad affermare il matematico e logico tedesco Leopold Kronecker, “Dio [ anche se io direi la Natura…] ha creato i numeri interi, tutto il resto è opera dell’uomo”.