Alessandro Zaccagnini ci propone un suo “Dialogo sui numeri primi”, un esercizio di stile in cui cercherà di parlare dei numeri primi in modo interessante senza usare formule, o quasi. Nel dialogo, che qui presentiamo a puntate, o meglio “giornate”, troveremo tre personaggi presi a prestito da Galileo: Salviati, che è un copernicano (un teorico dei numeri analitico), Sagredo, che è un patrizio (un matematico di un altro settore), e Simplicio, che è un tolemaico (un dilettante). Questa è la terza giornata, nella quale si discutono i metodi per determinare i numeri primi. Tutte le puntate le trovate sempre a questo link.

Giornata terza, nella quale si discutono i metodi per determinare i numeri primi

Salviati. Nella giornata di ieri abbiamo discusso dei metodi per determinare se un certo intero è o meno un numero primo. Oggi vogliamo affrontare un problema simile, e cioè determinare numeri primi, anche molto grandi.

Simplicio. Ho letto che i numeri primi grandi sono molto utili nelle applicazioni alla crittografia.

Salviati. Infatti, proprio cosí. Abbiamo bisogno di numeri primi grandi in alcuni crittosistemi moderni: ne parleremo ancora nella giornata che dedicheremo alle applicazioni. Per il momento parliamo di procedimenti per determinare tanti numeri primi simultaneamente.

Sagredo. Immagino che partiremo dal crivello di Eratostene.

Salviati. Per forza!

Simplicio. Mi aspettavo che ne avresti parlato.

Salviati. Tutti conoscono il crivello di Eratostene e quindi non ho bisogno di descriverlo in dettaglio. Il procedimento è molto noto: per parafrasare Sherlock Holmes, una volta eliminato tutto l’impossibile, quello che resta deve essere un numero primo.

Simplicio. In effetti, c’è la spiegazione nel mio libro delle medie.

Salviati. Quindi concordi con me che non è necessario parlarne a lungo. Preferisco concentrarmi su un aspetto importante dal punto di vista del calcolo che probabilmente non trovi nei tuoi libri.

Sagredo. Ti riferisci alla complessità computazionale, vero?

Salviati. Certamente. Cominciamo dal caso piú semplice. Vogliamo determinare tutti i numeri primi che non superano un certo intero \(N\); avremo dunque bisogno di \(N\) bit, che alla fine del calcolo conterranno l’informazione “primo” o “composto” relativamente all’intero corrispondente.

Sagredo. Questa è la quantità di memoria indispensabile.

Salviati. In realtà, ci sono delle semplici varianti che permettono di usarne di meno, ma non è importante descriverle qui. Eseguiamo il crivello utilizzando tutti i numeri primi che non superano la radice quadrata di \(N\), come ricordava ieri Simplicio, e alla fine di questo procedimento restiamo con il numero 1 e tutti i numeri primi fino ad \(N\).

Sagredo. Ma quante operazioni dobbiamo eseguire in totale?

Salviati. Per rispondere abbiamo bisogno di una formula scoperta da Frits Mertens nella seconda metà dell’Ottocento, parzialmente nota a Eulero già un secolo prima. Il numero totale di operazioni è poco piú grande del valore di \(N\) e quindi questo algoritmo è davvero efficiente.

Sagredo. Però ha bisogno di tanta memoria, o sbaglio?

Salviati. La quantità di memoria necessaria è proporzionale ad \(N\), anche usando le ottimizzazioni a cui alludevo prima.

Simplicio. E questo non va bene?

Salviati. Pone un limite alla sua applicabilità pratica, anche se al giorno d’oggi la memoria non è costosa come un tempo. Aggiungo subito che il crivello di Eratostene è sempre stato un algoritmo molto popolare, perché combina semplicità ed efficienza.

Simplicio. In effetti, è semplice da realizzare con un computer. Anche io ci sono riuscito!

Salviati. È cosí popolare e studiato che ne sono state realizzate alcune versioni migliorate che richiedono significativamente meno memoria. Il “crivello segmentato” richiede una quantità di memoria proporzionale alla radice quadrata di \(N\), mentre all’inizio del 2020 Harald A. Helfgott ha mostrato come una combinazione molto ingegnosa di idee relativamente semplici permette addirittura di scendere alla radice cubica di \(N\).

Sagredo. Quindi anche una cosa ben nota come il crivello di Eratostene continua ad essere argomento di ricerca attuale. E con l’aumentare della potenza dei computer, si può ben immaginare che la caccia al record non si esaurisca tanto rapidamente …

Salviati. Concludendo, alla domanda “Quanto è difficile trovare tutti i numeri primi fino ad \(N\)?” rispondiamo che se \(N\) è moderatamente grande possiamo usare il crivello di Eratostene.

Sagredo. Però, come ricordava stamattina Simplicio, per le applicazioni alla crittografia è indispensabile determinare qualche numero primo molto grande.

Salviati. Senza dover determinare tutti i numeri primi piú piccoli, perché abbiamo già notato che è una cosa impraticabile.

Sagredo. Per essere concreti: voglio un numero primo di 113 cifre decimali che comincia con 314159265. Posso trovarlo?

Salviati. Con una combinazione delle idee che abbiamo già discusso prima. Possiamo formalizzare il tuo problema dicendo che stiamo cercando un numero primo in un certo intervallo.

Simplicio. Cosa intendi dire?

Salviati. Prendiamo come obiettivo l’intervallo di numeri interi \([M, M + N]\), dove \(M\) è molto grande. Nell’esempio di Sagredo, \(M = 3.14159265 \cdot 10^{112}\).

Simplicio. E che ci facciamo con questo intervallo?

Salviati. Prendiamo \(N\) come abbiamo fatto prima, in modo che sia possibile fare il crivello di Eratostene su \(N\) interi consecutivi, come abbiamo detto qualche minuto fa quando abbiamo illustrato le nuove varianti.

Sagredo. Quindi \(N\) sarà molto piú piccolo di \(M\), dico bene?

Salviati. Dici benissimo; estremamente piú piccolo.

Sagredo. Ma, allora, se eseguiamo il crivello fermandoci alla radice quadrata di \(N\) non siamo sicuri che gli elementi dell’intervallo \([M, M + N]\) che sono sopravvissuti al crivello, per cosí dire, siano proprio dei numeri primi.

Simplicio. No? E perché?

Salviati. Perché ci fermiamo molto prima della loro radice quadrata.

Simplicio. E allora come si fa concludere?

Salviati. I risultati di Mertens a cui alludevo prima, e che citerò ancora molte volte nei prossimi giorni, garantiscono che gli interi “residui” sono relativamente pochi.

Sagredo. Quanto pochi?

Salviati. Se \(N\) ha 20 cifre decimali, resta circa un intero ogni 45.

Sagredo. E cosa fai con questi interi? Non puoi sapere se sono numeri primi o composti con fattori molto grandi.

Salviati. La maggioranza di questi sono composti, in effetti.

Simplicio. E allora come fai a distinguerli?

Salviati. Possiamo usare tecniche ad hoc su ciascuno di questi, come quelle che abbiamo discusso nella seconda giornata. Per esempio, ricorderai i nomi di Miller-Rabin, e non solo.

Simplicio. Sí, certo, ne abbiamo discusso a lungo.

Salviati. Siccome i numeri residui non sono molti, possiamo procedere utilizzando questi metodi, che sono relativamente piú onerosi.

Sagredo. [Sorride] Stai cercando di vivere nel migliore dei mondi possibili. Usi il crivello là dove è efficiente e poi usi un altro metodo.

Salviati. Esatto. Simplicio, secondo te, quando hai trovato un numero primo come quello che voleva Sagredo, che te ne fai?

Simplicio. Non saprei. Che faccio?

Salviati. Lo vendi!

Simplicio. A chi?

Salviati. A qualcuno che ne ha bisogno per la crittografia.

Sagredo. E questo qualcuno ti deve credere sulla parola?

Salviati. Niente affatto. Questo è il bello dei numeri primi.

Sagredo. Non capisco dove vuoi arrivare.

Salviati. Metti che incontri qualcuno alla stazione, diciamo la sera tardi, che ti proponga di acquistare un orologio d’oro. Tu che fai?

Sagredo. Me ne guardo bene!

Salviati. Anche se promettesse di darti un certificato di garanzia?

Sagredo. Beninteso! Sarebbe folle da parte mia accettare, certificato o no.

Simplicio. Sarebbe falso anche il certificato e non solo l’orologio.

Salviati. Ovviamente. Ma se ti offrisse un numero primo con il certificato di garanzia, potresti verificare il certificato e acquistare il numero primo senza paura di fregature.

Simplicio. Davvero?

Salviati. Partendo dal Piccolo Teorema di Fermat, nel diciannovesimo secolo il matematico francese Édouard Lucas ha scoperto un criterio di primalità, che oggi non è piú usato perché se ne conoscono di migliori. Nel 1975 Vaughan Pratt lo ha modificato, trasformandolo in quello che vi dicevo, cioè un modo pratico per certificare che un numero intero \(p\) è effettivamente primo.

Sagredo. E come funziona?

Salviati. Funziona ricorsivamente. Devi scomporre in fattori primi il numero \(p – 1\) e dimostrare che tutti questi fattori sono effettivamente primi a loro volta; in pratica, ogni certificato è fatto di certificati piú piccoli che, messi insieme, danno la dimostrazione della primalità di \(p\).

Simplicio. Credevo che scomporre in fattori primi fosse un problema abbastanza difficile.

Salviati. Lo è, in effetti. Ma l’onere della prova è sul venditore: tocca a chi vende generare il certificato. La verifica di un certificato, invece, è un’operazione piuttosto semplice, anche per numeri di 113 cifre come quello che ci ha chiesto Sagredo.

Sagredo. Salviati, ora che hai menzionato il problema, lo vedi anche tu che devi fare almeno qualche cenno alla scomposizione in fattori primi di un numero intero. Non puoi lasciarci con la curiosità.

Salviati. Determinare i fattori primi di un dato intero è un problema molto famoso e studiato. Carl F. Gauss, chiamato anche il principe della matematica, ne parla nelle sue Disquisitiones Arithmeticæ del 1801, lo stesso libro in cui introduce e tratta sistematicamente le congruenze, e dice che è giusto dedicare ogni sforzo alla sua soluzione.

Simplicio. Ma non basta verificare che il numero dato non sia divisibile per tutti gli interi fino alla sua radice quadrata? Sul mio libro c’è scritto cosí.

Salviati. Dobbiamo di nuovo distinguere fra numeri “grandi” e “piccoli.” Per i numeri molto piccoli quello che dici va bene, perché è un’idea facile da implementare.

Simplicio. È vero, io stesso ho scritto un programma per computer per scomporre in fattori primi in questo modo.

Salviati. E per quali numeri funziona?

Simplicio. L’ho provato con numeri interi fino a \(2^{32}\), quelli che mi fornisce il mio computer.

Sagredo. Ma \(2^{32}\) vale circa 4 miliardi, e penso che Salviati lo consideri un numero piccolo.

Salviati. Ci puoi scommettere!

Sagredo. E per i numeri “grandi” cosa possiamo fare?

Salviati. Se insistiamo a cercare fattori primi fino alla radice quadrata del numero dato la complessità computazionale è molto alta; quindi ci dobbiamo fermare ben prima.

Simplicio. E se salti qualche fattore primo?

Salviati. Dobbiamo usare una combinazione di tecniche diverse. Per prima cosa, verifichiamo se il numero dato ha fattori primi molto piccoli e in questo caso li eliminiamo.

Simplicio. Ma il numero che ti resta potrebbe avere dei fattori molto grandi.

Salviati. Infatti, la cosa da fare è verificare che il numero residuo \(N\) sia composto, usando uno dei metodi che abbiamo discusso ieri mattina.

Sagredo. Altrimenti rischi di fare un sacco di lavoro inutile, cercare di scomporre in fattori primi un numero che è primo!

Salviati. Esattamente. Quindi ora abbiamo un numero composto \(N\), che non ha fattori primi molto piccoli: e qui torna in gioco Fermat.

Simplicio. Che c’entra Fermat?

Salviati. Ha proposto un metodo alternativo per scomporre in fattori primi. Funziona cosí: parti dal numero \(N\) ed aggiungi 1; poi controlli se il risultato è un quadrato perfetto. Se no, aggiungi 4 al numero \(N\) e di nuovo controlli se è un quadrato perfetto. Se no, aggiungi 9, poi 16, poi 25, e cosí via, …

Sagredo. E questo algoritmo termina?

Salviati. Sí, se parti da un numero \(N\) dispari, prima o poi trovi un quadrato perfetto.

Simplicio. E cosa te ne fai?

Salviati. Hai appena trovato due interi \(x\) ed \(y\) per cui \(N + y^2 = x^2\).

Sagredo. Fammi capire: hai scoperto che \(N = x^2 – y^2\)!

Simplicio. E allora?

Sagredo. E allora ti ricordi del “prodotto notevole” \(x^2 – y^2 = (x – y) \cdot (x + y)\) e hai scomposto \(N\) in fattori!

Simplicio. E funziona davvero?

Salviati. Certo che funziona!

Simplicio. E allora perché non lo usate?

Sagredo. Per colpa della solita complessità computazionale, immagino.

Salviati. Infatti, proprio cosí.

Simplicio. È frustrante scoprire che le cose funzionano ma non le puoi usare.

Salviati. Ma non tutto è perduto! Negli anni ’70 del ventesimo secolo, R. Sherman Lehman ha osservato che l’algoritmo della “divisione per tentativi,” di cui parlava Simplicio, fa fatica a scomporre in fattori i numeri interi \(N\) che sono divisibili per pochi numeri primi relativamente grandi.

Sagredo. Se sono grandi, sono per forza pochi.

Salviati. Infatti. Al contrario, l’idea di Fermat permette di trovare facilmente i fattori piú grandi, e fa fatica con quelli piccoli.

Sagredo. In un certo senso sono complementari, dunque.

Simplicio. Cosa vuoi dire?

Sagredo. A quanto ci ha appena detto Salviati, i punti di forza di un algoritmo sono i punti di debolezza dell’altro, e viceversa.

Salviati. Partendo da questo, Lehman ha combinato due tecniche e ha inventato un algoritmo che permette di fare la divisione per tentativi solo fino alla radice cubica di \(N\), e poi passare ad una variante molto ingegnosa dell’idea di Fermat.

Simplicio. E come fai ad essere proprio sicuro di non aver trascurato nessun fattore primo grande?

Salviati. Usando idee che provengono dalla teoria delle frazioni continue Lehman ha dimostrato rigorosamente che il numero \(N\) viene effettivamente scomposto in tutti i suoi fattori, perché quelli grandi sono scoperti nella seconda fase del suo algoritmo. Il grande vantaggio di questa seconda fase è il fatto che il numero di “tentativi” che devi fare prima di scomporre \(N\) in fattori è molto basso.

Sagredo. Ci sono stati sviluppi, negli ultimi decenni?

Salviati. Diversi. Dal nostro punto di vista il piú interessante è questo: invece di “risolvere” l’equazione di Fermat \(N = x^2 – y^2\) si cerca di risolvere l’equazione \(x^2 \equiv y^2 \mod N\).

Sagredo. Una congruenza al posto di un’equazione fra numeri interi.

Simplicio. E quale sarebbe il vantaggio? Si devono pur sempre cercare dei numeri interi che soddisfano la congruenza.

Salviati. Il vantaggio è visibile a posteriori, perché l’equazione di Fermat ha relativamente poche soluzioni mentre la congruenza ne ha relativamente tante. C’è una complicazione ulteriore perché alcune di queste soluzioni non portano ad una scomposizione di \(N\) in fattori, ma in ogni caso gli algoritmi di questo tipo si sono rivelati estremamente efficaci.

Sagredo. Perché parli al plurale?

Salviati. Perché in realtà sono stati scoperti molti modi diversi per risolvere questa congruenza. L’idea di base è la stessa, ed è dovuta al matematico belga Maurice Kraitchik, ma i diversi algoritmi usano principi matematici diversi per raggiungere il loro scopo.

Sagredo. Puoi dirci almeno due parole?

Salviati. I due algoritmi moderni che detengono il primato sono il crivello quadratico e il crivello con i campi di numeri: come suggerisce il nome basano la loro efficienza sull’uso di procedimenti iterativi simili al crivello di Eratostene. Ti ricordo che il crivello funziona bene perché permette di trattare molti interi simultaneamente, una classe di resto alla volta; però entrare nei dettagli ci porterebbe decisamente fuori strada.

Simplicio. È troppo difficile da spiegare?

Salviati. Per capire il funzionamento del crivello con i campi di numeri servono buone conoscenze di algebra, come le estensioni finite dei numeri razionali. Il crivello quadratico, invece, in linea di principio richiede solo conoscenze relativamente elementari, ma ad ogni modo non può essere spiegato in una chiacchierata come la nostra.

Sagredo. Ti manca la lavagna? Vuoi che ne faccia montare una?

Salviati. Per carità, Sagredo, ti ringrazio ma non dirlo nemmeno per scherzo! Godiamoci la tranquillità della nostra conversazione informale!

Simplicio. Puoi suggerirmi un libro dove posso approfondire?

Sagredo. Su questo tavolino troverai molti libri e articoli divulgativi che Salviati mi ha segnalato in vista di queste nostre chiacchierate e che sono a tua disposizione.

Simplicio. Dopo pranzo, cercherò di studiare un po’.

Sagredo. [A parte] Può farti un gran bene …

Salviati. Hai bisogno di sapere qualcosa sulle congruenze e sui polinomi, sulla soluzione di equazioni di secondo grado modulo numeri primi, e per concludere un bel ripasso del metodo di eliminazione di Gauss.

Sagredo. Non è una cosa di algebra lineare?

Salviati. Esatto. L’idea di Kraitchik è di generare tante congruenze “parziali” da combinare per ottenere una o piú soluzioni dell’equazione \(x^2 \equiv y^2 \mod N\); questa ricerca può essere svolta in modo efficiente usando, come dicevo, un’idea simile al crivello. Un’altra cosa molto bella è che questa fase del calcolo può essere distribuita su tanti processori che lavorano in parallelo.

Sagredo. E Gauss?

Salviati. Il metodo di eliminazione serve appunto nella fase in cui le congruenze già trovate vengono combinate per trovare le soluzioni cercate.

Sagredo. Qual è il limite degli algoritmi attuali?

Salviati. Qualche centinaio di cifre decimali: il record attuale è intorno alle 250 cifre.

Simplicio. Ma ieri hai parlato di numeri molto piú grandi.

Sagredo. Ieri abbiamo parlato dei numeri di Mersenne.

Salviati. Questo non è in contraddizione con il record che riguarda il piú grande numero primo di Mersenne. Come ho ricordato prima, si usa un algoritmo ad hoc che funziona esclusivamente per i numeri di Mersenne, e comunque cerchiamo solo di determinarne la primalità.

Simplicio. Non capisco.

Salviati. Al giorno d’oggi è plausibile scomporre in fattori primi numeri interi di 250 cifre, usando molti computer che lavorano in parallelo. Per stabilire sempre nuovi record, invece, si devono scegliere numeri molto speciali, ma sempre nel caso della determinazione della primalità.

Simplicio. Continuo a non capire.

Sagredo. Salviati vuol dire che se scegli a caso un numero intero di 200-250 cifre, gli algoritmi e i computer attuali sono in grado di scomporlo in fattori. Per alcuni interi molto speciali come i numeri di Mersenne esistono metodi costruiti su misura, ma solo per decidere se sono primi o composti.

Salviati. E comunque, anche se dimostri che un certo numero di Mersenne è composto, molto difficilmente riuscirai a determinare i suoi fattori. Qualcuno sí, ma la fattorizzazione completa è molto difficile da ottenere.

Sagredo. Essendo l’ora di pranzo, vi invito a sospendere momentaneamente la nostra discussione per aggiornarla davanti a un bel piatto di pasta. Che ne dite?

Fine della terza giornata

(L’immagine di copertina è presa da qui)