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 seconda giornata, nella quale si discutono i metodi per distinguere i numeri primi dai numeri composti. Tutte le puntate le trovate sempre a questo link.

Giornata seconda, nella quale si discutono i metodi per distinguere i numeri primi dai numeri composti

[La scena si apre come il giorno prima. Cambia la posizione delle carte sul tavolino e la quantità di frutta e dolci a disposizione]

Salviati. Ora che ci siamo accordati sull’oggetto del nostro studio e abbiamo una definizione condivisa, possiamo cominciare a farci qualche domanda sui numeri primi.

Sagredo. La prima, direi, è come si fa a distinguere un numero primo da un numero composto.

Simplicio. Questo è abbastanza facile: basta verificare la definizione che abbiamo concordato ieri. E poi, in realtà non è necessario controllare che l’intero in questione non abbia altri divisori oltre ad 1 e sé stesso: basta arrivare alla sua radice quadrata: questo lo sanno tutti.

Salviati. Per i numeri relativamente piccoli, in effetti questa è la cosa piú semplice da fare.

Sagredo. Per i numeri grandi no?

Salviati. Per i numeri grandi è piú adatto un approccio indiretto. L’algoritmo ricordato da Simplicio, in realtà, dà piú informazioni di quelle richieste: non ti dice solo se il numero è primo o composto, ma nel secondo caso ne fornisce anche una parziale scomposizione in fattori primi.

Simplicio. Che male c’è?

Salviati. Dipende dalla fatica che devi fare per procurarti questa informazione. Come direbbero gli informatici, è una questione di complessità computazionale: esistono metodi molto efficienti per certificare che un dato intero è composto senza per questo fornirne la scomposizione.

Simplicio. Che cos’è la complessità computazionale?

Sagredo. È la quantità di risorse di cui ha bisogno un algoritmo per essere portato a termine. Con la parola risorse intendiamo sia il numero di operazioni da eseguire che la quantità di memoria occupata.

Simplicio. Ma i computer oggi sono molto veloci e hanno grandi quantità di memoria.

Salviati. Certo, ma per sapere se un numero di 100 cifre è composto può bastare qualche secondo, mentre per avere la sua scomposizione possono essere necessari parecchi giorni e molti computer che lavorano in parallelo.

Sagredo. Ma riprendiamo il discorso che Salviati ha cominciato poco fa: come è possibile dimostrare indirettamente che un certo numero è primo oppure composto?

Simplicio. A me sembra una contraddizione in termini: se non conosci i suoi fattori primi, come puoi dire con certezza che un numero è composto?

Salviati. No, Simplicio, non è una contraddizione se hai mai sentito parlare del Piccolo Teorema di Fermat, per esempio.

Simplicio. Sí, ora che me ne parli, ricordo che c’era in un libro che ho letto anni fa, scritto da Conway & Guy.

Salviati. È un bellissimo libro. Dunque ricordi che, limitandoci per il momento ad un caso particolare, se \(p\) è un numero primo allora \(p\) divide \(2^p – 2\).

Simplicio. Questo me lo ricordo, ma non capisco cosa c’entri.

Salviati. Se vuoi sapere se un certo numero \(n\) è primo, calcoli \(2^n – 2\). Se questo numero non è divisibile per \(n\) allora \(n\) non può essere primo.

Sagredo. Scusa, Salviati, ma se \(n\) è un numero grande come dicevi prima, allora \(2^n – 2\) è veramente enorme.

Salviati. Hai ragione, naturalmente, ma ci interessa solo sapere se è divisibile per \(n\).

Simplicio. Non capisco.

Salviati. Ci sono delle scorciatoie che permettono di calcolare in modo efficiente il valore del resto della divisione di \(2^n – 2\) per \(n\) senza dover calcolare veramente il valore di \(2^n – 2\), e facendo “poche” operazioni.

Sagredo. Ne ho sentito parlare: per calcolare \(2^n\) non si deve applicare la definizione di potenza, ma si procede in un modo completamente diverso.

Salviati. Sí, ti riferisci al metodo dei “quadrati ripetuti.”

Sagredo. Mi hai convinto, Salviati, ma ho ancora una domanda da farti. Se \(2^n – 2\) non è divisibile per \(n\), abbiamo detto che \(n\) è necessariamente composto, anche se non abbiamo idea di quali possano essere i suoi fattori primi.

Salviati. Precisamente.

Simplicio. Hai convinto anche me, alla fine.

Sagredo. La mia domanda è questa: se \(2^n – 2\) è divisibile per \(n\), allora \(n\) è necessariamente primo?

Salviati. Purtroppo no. Esistono alcuni interi composti \(n\) per cui \(2^n – 2\) è divisibile per \(n\); il piú piccolo è 341. All’inizio del ventesimo secolo, il matematico palermitano Michele Cipolla ha dimostrato che sono infiniti, anche se sono relativamente rari.

Simplicio. Ma io ricordo che il Teorema di Fermat era enunciato in modo diverso.

Salviati. Ricordi bene, Simplicio. Dato un qualsiasi intero \(a\), se \(p\) è un numero primo allora \(a^p – a\) è divisibile per \(p\).

Sagredo. Questo cambia tutto, o no? Fai la prova con \(a = 2\), poi con \(a = 3\), poi con \(a = 4\) e cosí via. Se \(n\) non è primo, uno di questi casi te lo dovrà rivelare.

Salviati. Purtroppo le cose non sono cosí semplici. Altri matematici hanno studiato questo problema piú o meno contemporaneamente a Cipolla; ricordiamo R.D. Carmichael e A. Korselt, i quali hanno scoperto che esistono alcuni interi \(n\) particolarmente riottosi che, pur essendo composti, dividono \(a^n – a\) qualunque sia l’intero \(a\).

Sagredo. E quindi “fingono” di essere primi?

Salviati. In un certo senso, possiamo dire cosí. La condizione di Fermat è solo necessaria per la primalità, e non sufficiente.

Simplicio. Ma quanti sono questi numeri composti un po’ speciali? Se fossero in numero finito basterebbe calcolare il piú grande e poi potremmo usare il teorema di Fermat da lí in avanti.

Salviati. Bella domanda davvero, Simplicio, però purtroppo non è cosí. Nel 1994, W.R. Alford, A. Granville e C. Pomerance hanno dimostrato che sono infiniti, e che non sono rarissimi.

Sagredo. Dunque non possiamo usare questo tipo di test per dimostrare che un numero è primo.

Salviati. In conclusione, la condizione di Fermat è molto utile ma non risolutiva. Dimostra in modo inequivocabile che certi interi sono composti, ma non riesce a distinguere alcuni numeri composti dai numeri primi.

Sagredo. E quindi la verifica della primalità attraverso la condizione di Fermat è stata abbandonata?

Salviati. No, perché è un tipo di condizione facile da verificare, e quindi generazioni di matematici hanno cercato dei modi per “aggirare” i suoi difetti.

Simplicio. Non capisco cosa vuoi dire.

Salviati. La condizione di Fermat, da sola, permette di individuare quasi tutti, ma non proprio tutti, i numeri composti. Come dicevo, è una condizione necessaria per la primalità, ma non sufficiente.

Sagredo. Anche cambiando il numero \(a\), qualche numero composto continua a “fingere” di essere primo.

Salviati. Esattamente. Sono state cercate altre condizioni, magari un po’ piú difficili da verificare, che permettano di eliminare tutti i numeri composti. Una delle piú note è quella alla base dell’algoritmo di Miller-Rabin, che però è di natura probabilistica.

Sagredo. Cosa significa?

Salviati. Significa che se l’algoritmo risponde che il numero dato è composto, allora lo è veramente. In caso contrario, l’algoritmo dice che il numero dato è molto probabilmente un numero primo, ma non possiamo avere la certezza che lo sia.

Simplicio. Ma allora, perché usarlo?

Salviati. Perché è leggermente piú efficiente della verifica della condizione di Fermat, e inoltre è possibile dare una stima abbastanza accurata della probabilità che un numero composto non sia identificato come tale e continui a “fingere” di essere primo.

Sagredo. E non c’è un criterio che sia allo stesso tempo semplice e certo?

Salviati. È stato cercato per molto tempo, ma solo nel 2004 tre informatici indiani, M. Agrawal, N. Kayal e N. Saxena, sono finalmente riusciti a trovare una condizione necessaria e sufficiente, che è efficiente sulla carta ma difficile da implementare.

Sagredo. In che senso?

Salviati. Si può dimostrare che il numero totale di operazioni da effettuare per portare a termine questo tipo di verifica cresce lentamente con il numero in questione, molto piú lentamente dei test deterministici noti fino ad allora. D’altra parte, invece di fare calcoli con gli interi entrano in gioco polinomi di grado alto e questo presenta dei problemi di realizzazione pratica.

Sagredo. Capisco. Dal punto di vista dell’implementazione è chiaramente molto piú difficile da realizzare rispetto alla semplice aritmetica con numeri interi anche molto grandi.

Salviati. Anche perché esistono molte librerie già pronte e molto efficienti per l’aritmetica con i numeri interi arbitrariamente grandi.

Simplicio. E allora?

Salviati. Allora si preferisce continuare ad usare la proprietà di Miller-Rabin, che pur avendo le limitazioni di cui abbiamo discusso prima è molto facile da implementare.

Sagredo. Non si possono usare altri metodi per decidere se un dato intero è primo o no?

Salviati. In effetti, conosco almeno un’altra proprietà dei numeri primi che permette di dare una condizione necessaria e sufficiente: quella che deriva dal Teorema di Wilson.

Simplicio. Mi sembra di averne sentito parlare.

Salviati. È molto probabile: si trova in tutti i libri divulgativi. Il procedimento è questo: dato un intero \(n \ge 2\), calcoliamo \((n – 2)!\), dividiamo il risultato per \(n\) e poi prendiamo il resto di questa divisione. Questo resto vale 1 se e soltanto se \(n\) è un numero primo. Per \(n = 4\) il resto vale 2, per tutti gli altri numeri composti il resto vale 0.

Simplicio. E perché dici che questo criterio è inutile?

Sagredo. Ti rispondo io: per dimostrare che 101 è un numero primo devi calcolare \(99!\), cioè un prodotto con 99 fattori. A parte il fatto che il risultato è enorme, devi davvero fare una quantità esagerata di calcoli.

Salviati. Siccome ci interessa solo il resto, e non il valore esatto di questo numero, potremmo accorciare un po’ i calcoli e ridurre la dimensione dei risultati intermedi. Ma comunque non è un metodo pratico per determinare se un intero \(n\) è un numero primo oppure no.

Simplicio. Quindi il Teorema di Wilson non può essere usato?

Salviati. No, in pratica no. Avere una condizione necessaria e sufficiente può essere, paradossalmente, piú interessante dal punto di vista teorico che pratico.

Sagredo. E comunque la verifica della condizione di Wilson è impraticabile dal punto di vista computazionale.

Salviati. Del tutto impraticabile. Come spesso succede, la dimostrazione risulta un esercizio interessante, ma poi finisce lí!

Sagredo. Comunque, resta sorprendente la quantità di modi diversi in cui possiamo caratterizzare i numeri primi, non credi?

Salviati. E ce ne sono anche tanti altri.

Simplicio. Cambiando discorso, Salviati, mi sai dire qual è il record? Il piú grande numero primo conosciuto?

Salviati. Che io sappia, è un numero di quasi 25 milioni di cifre. Sai chi era Marin Mersenne?

Simplicio. Non credo di averlo mai sentito nominare.

Salviati. Era un monaco vissuto nel diciassettesimo secolo, che aveva tra i suoi corrispondenti scientifici Descartes, Pascal, Galilei ed altri importanti matematici e filosofi. Con le sue lettere diffondeva il sapere tra i suoi amici ed ha avuto un ruolo molto importante.

Simplicio. E cosa c’entra Mersenne con il piú grande numero primo conosciuto?

Salviati. Oltre ad aver favorito la diffusione delle conoscenze del suo tempo, ha dato anche qualche contributo originale alla matematica. In questo caso, ha fatto un’affermazione che si è rivelata scorretta, ma molto fruttuosa.

Simplicio. Sembra una contraddizione.

Sagredo. Immagino che Salviati voglia dire che i matematici successivi hanno cercato di dimostrare o confutare l’affermazione di Mersenne, e questo ha stimolato sempre nuove ricerche. D’altronde, la stessa cosa è successa, su una scala molto piú grande, con l’ultimo teorema di Fermat che piú o meno è dello stesso periodo.

Simplicio. Ah, sí, conosco la storia. Ho letto il libro di Simon Singh.

Sagredo. [A parte] Male!

Salviati. Tornando a Mersenne, ha dato una lista di numeri primi \(p\) per i quali è primo anche il numero \(2^p – 1\). Purtroppo questa lista contiene vari errori e anche qualche omissione.

Sagredo. Ma perché Mersenne si interessava a questi numeri?

Salviati. Perché Euclide ha dimostrato che sono legati ai numeri perfetti.

Simplicio. Cosa sono i numeri perfetti?

Salviati. Sono gli interi come 6 o 28 che sono uguali alla somma dei propri divisori, escludendo i numeri stessi.

Simplicio. Fammi controllare.

[Simplicio prende un foglio dal tavolino e fa qualche calcolo.]

Simplicio. Sí, è vero. 6 è uguale a \(1 + 2 + 3\), mentre 28 è uguale a \(1 + 2 + 4 + 7 + 14\).

Salviati. Il successivo è 496. Euclide ha dimostrato che se \(2^p – 1\) è un numero primo, si ottiene un numero perfetto moltiplicandolo per \(2^{p – 1}\).

Simplicio. Fammi provare.

[Simplicio fa altri calcoli. Nell’attesa, Salviati e Sagredo si versano un bicchiere di bibita e parlano fra loro a bassa voce.]

Simplicio. Hai ragione! Quando \(p\) vale 5, 31 è un numero primo e \(31 \cdot 16\) vale 496 ed è un numero perfetto.

Salviati. Come abbiamo già osservato prima, se \(p\) è un numero grande, che sia primo o meno, \(2^p – 1\) è chiaramente enorme, ma nei secoli sono stati escogitati molti metodi indiretti ad hoc per verificare se sia primo, senza doverlo calcolare davvero.

Sagredo. E questo permette di stabilire sempre nuovi record?

Salviati. Esatto.

Simplicio. Ma record a parte, i numeri perfetti hanno qualche utilità?

Salviati. Non che io sappia.

Sagredo. Sono infiniti?

Salviati. Se ne conoscono solo 51, ma si pensa che siano infiniti. Forse è la piú antica congettura aperta della matematica.

Sagredo. Non ne avevo la minima idea!

Salviati. Concludiamo la discussione per questa giornata sottolineando di nuovo un aspetto che possiamo considerare sorprendente a prima vista, e cioè che alcune dimostrazioni possono essere indirette: non sempre è necessario verificare direttamente le definizioni. Come abbiamo discusso prima, esistono delle proprietà condivise da tutti i numeri primi che sono relativamente facili da verificare.

Simplicio. Intendi dire che i calcoli che dobbiamo fare non sono troppo lunghi?

Salviati. Oppure che non abbiamo bisogno di molta memoria.

Sagredo. Ma ora andiamo perché ci aspetta un buon pranzo. E piú tardi, dopo un pomeriggio passato al mare, ci potremo rilassare con un’oretta di musica da camera.

Fine della seconda giornata

(L’immagine di copertina è presa da qui)

Alessandro Zaccagnini