SECONDA PARTE

 

In questo secondo articolo della serie incominciata con [5] riprendiamo la descrizione di alcune proprietà elementari dei numeri primi. Cominciamo con il secondo punto dell'elenco esposto nel §4 dell'articolo già citato.

 

Come riconoscere i numeri primi e come scomporre in fattori primi

Vogliamo subito precisare che il problema di dimostrare la primalità di un intero è cosa diversa da quella di ricercarne gli eventuali fattori. Infatti esistono dei risultati che garantiscono la primalità di un numero mediante opportune condizioni equivalenti; il fatto che tali condizioni risultino non verificate consente quindi di concludere che tale numero è composto senza doverne esibire un divisore. Per essere utili in pratica tali condizioni devono però coinvolgere oggetti matematici “semplici” e richiedere per la loro verifica un quantità di calcoli limitata.
Cominciamo la nostra presentazione esaminando una condizione necessaria e sufficiente per la primalità che utilizza solamente delle congruenze: il famoso Teorema di Wilson di cui diamo una dimostrazione nel §3.1 di [4].

Teorema 1.1 (Wilson) L'intero n ≥2 è primo se e solo se (n-1)!≡ -1 mod n.

Per esempio, (10-1)!=362880≡0-1 mod 10, e quindi 10 non è un numero primo, mentre (13-1)!= 479001600≡-1 mod 13 e quindi 13 è un numero primo. Chiaramente l'enunciato del Teorema di Wilson 1.1 non richiede alcuna conoscenza sui fattori di n ma si basa solamente sulla verifica di una opportuna congruenza che coinvolge n. Sfortunatamente in questo caso la quantità di calcoli da effettuare per verificare la congruenza è proporzionale a n stesso e quindi il Teorema di Wilson non può essere utilizzato in pratica per verificare la primalità di un intero “grande” perché richiederebbe un'attesa troppo lunga prima di ottenere una risposta.


Pierre de Fermat
Esistono però altri risultati che, sebbene non costituiscano una condizione equivalente alla primalità di un intero, possono essere verificati con un numero di calcoli estremamente più contenuto; un esempio famoso è il Piccolo Teorema di Fermat. Data la sua enorme importanza, diamo una dimostrazione del Piccolo Teorema di Fermat diversa dalle due che abbiamo incluso in [4], e di natura combinatoria.

Questa dimostrazione ci pare particolarmente interessante perché non fa uso di concetti complicati (neppure delle congruenze che pure non sono particolarmente complesse) ma sfrutta solo il conteggio di opportuni oggetti, e quindi non richiede alcuna nozione preliminare, ma solo del buon senso comune. Questa, come altre dimostrazioni elementari di teoremi importanti, si trova in Mortola [6].

Figura 1: Dimostrazione del Piccolo Teorema di Fermat: le 64 collane con 3 perline di 4 colori; quelle policrome sono raggruppate in classi di collane equivalenti per rotazione.

Teorema 1.2 (Piccolo Teorema di Fermat) Sia a un intero qualsiasi, e p un numero primo. Allora apa mod p.

Dim. Consideriamo tutte le collane con p perline, ciascuna delle quali può avere uno qualsiasi fra a colori diversi. Vi sono evidentemente ap collane possibili, a delle quali sono monocromatiche. Suddividiamo le rimanenti ap-a collane (policrome, cioè con perline di almeno due colori diversi) in classi di equivalenza, come segue: due collane sono equivalenti se una si ottiene dall'altra mediante un'opportuna rotazione del piano. Evidentemente ogni classe non può contenere più di p collane fra loro equivalenti, ma, poiché p è primo, per il Lemma 1.3 ogni classe ne deve contenere esattamente p. Dunque, p divide ap-a.

La Figura 1 illustra la dimostrazione nel caso p=3, a=4.

Figura 2: La dimostrazione del Lemma 1.3. La collana è invariante per una rotazione in senso orario di 4 perline, e quindi, scelte in modo arbitrario 4 perline consecutive, a sinistra, sappiamo che le 4 perline immediatamente adiacenti, sempre in verso orario, devono essere colorate allo stesso modo. Per lo stesso motivo, anche le successive 4 hanno la stessa colorazione, e così via: il numero totale di perline deve essere un multiplo di 4, e quindi non è primo.

Lemma 1.3 Se p è un numero primo, nessuna collana policroma con p perline è equivalente ad una propria rotazione non banale.

Dim. Supponiamo che la collana data sia equivalente alla propria rotazione in senso orario di r perline, con r>1 (altrimenti la collana sarebbe monocromatica) ed r<p (altrimenti la rotazione sarebbe banale). Fissiamo r perline consecutive. Le r perline successive a quelle fissate devono formare un blocco uguale alle r precedenti (dato che dopo la rotazione vanno a coincidere). In altre parole, la collana è formata da due blocchi identici consecutivi di r perline ciascuno, seguite da p-2r perline. Possiamo ripetere lo stesso identico ragionamento per le ulteriori r perline successive, che devono a loro volta formare un altro blocco uguale ai due precedenti, dando luogo a 3 blocchi identici consecutivi seguiti da p-3r perline. Iterando questo procedimento fino ad esaurire tutte le perline della collana senza tralasciarne nessuna, troviamo che questa è costituita da k blocchi di r perline ciascuno. In definitiva, r|p e p non è un numero primo.

È opportuno notare che, se p è primo, la rotazione di una collana produce una collana diversa, mentre questo non è vero se p non è primo, come si vede dal caso con p=20 illustrato dalla Figura 2.
Per esempio, abbiamo 291≡37 mod 91, e quindi 91 non è un numero primo. Analogamente a quanto visto sopra per il Teorema di Wilson, questa è solo una dimostrazione “indiretta” del fatto che 91 non è primo, ed infatti non ne vengono ricavati i fattori primi. La situazione è resa più complicata dal fatto che mentre la congruenza di Wilson dà una condizione necessaria e sufficiente per la primalità, la congruenza di Fermat dà solo una condizione necessaria. In effetti, 391≡3 mod 91, nonostante il fatto che 91 non è un numero primo.


Carl Pomerance
Osserviamo che, da un punto di vista computazionale, il calcolo di an mod n è poco oneroso (si veda per esempio il §6.9.2 di [4], oppure [9]) e quindi è naturale pensare a come il Piccolo Teorema di Fermat possa essere utilizzato per la verifica della primalità di un intero.

In pratica si prova a vedere se il numero n verifica ana mod n per varie scelte di a∈Z. Notiamo che, in realtà, possiamo ridurci al caso (a,n)=1, 0≤a<n , e verificare, in tale situazione, che an-1≡1 mod n. Per analizzare il significato della risposta ci serve il seguente

Lemma 1.4 Se n è composto ed esiste b∈Z con (b,n)=1 e 0≤b<n tale che bn-11 mod n, allora an-11 mod n per almeno la metà degli interi aZ con (a,n)=1 e 0≤a<n.

Allora, dopo il primo a usato, possiamo concludere che o n è probabilmente un numero primo con probabilità maggiore o uguale a 1-1/2 o n è un numero composto che verifica an-1≡1 mod n per tale a.
Ripetendo il test k volte cambiando a ogni volta, si ottiene che o n è primo con probabilità maggiore o uguale a 1-(1/2)k oppure n è composto e verifica la congruenza an-1 ≡1 mod n per tutti gli a utilizzati.
A prima vista questa situazione pare non essere troppo svantaggiosa: abbiamo un test piuttosto facile da implementare e notevolmente performante che fornisce una risposta che sembra ragionevolmente buona. Sfortunatamente, però, esistono interi composti n per cui an-11 mod n per ogni a∈Z con (a,n)=1. Tali interi sono detti numeri di Carmichael; ad esempio 561=3·11·17 è un numero di Carmichael. Quindi esistono interi composti che “fingono” di essere primi rispetto alla congruenza del Piccolo Teorema di Fermat per ogni possibile scelta di a. Il fatto è spiacevole, ma se i numeri di Carmichael fossero finiti potremmo ancora ottenere un algoritmo di primalità molto buono precalcolandoli tutti. Purtroppo, nel 1994, Alford, Granville e Pomerance hanno dimostrato che esistono infiniti numeri di Carmichael e quindi la congruenza del Piccolo Teorema di Fermat non può essere utilizzata per caratterizzare algoritmicamente i numeri primi.
In altre parole, un intero a tale che na ed an-11 mod n è una prova certa del fatto che n non è un numero primo (se n fosse primo si avrebbe an-1≡1 mod n per il Piccolo Teorema di Fermat, contraddizione) mentre un intero a tale che na ed an-1 ≡1 mod n fornisce solo un indizio della primalità di n, ed in questo caso non è vero che tre indizi fanno una prova a causa dei numeri di Carmichael...
È possibile, però, utilizzare alcune varianti più sofisticate del Piccolo Teorema di Fermat. Esse utilizzano un insieme finito di congruenze della stessa tipologia di quelle viste poco sopra ma, a differenza del caso precedente, per esse è dimostrato che, se n è composto, esiste un a per cui tali congruenze non sono valide (ossia per tale insieme di congruenze non esiste un concetto analogo a quello dei numeri di Carmichael).
Senza entrare nel dettaglio, essenzialmente si “estraggono” tutte le possibili radici quadrate di an-1 mod n e, se n è primo, si osserva che tali radici quadrate devono essere tutte uguali a 1 o a -1. Nel caso in cui una di esse non sia ± 1 allora n è composto. Anche in questo caso si può valutare probabilisticamente la correttezza della risposta al variare di a.
Il fatto che questo test (algoritmo di Miller-Rabin) sia anch'esso computazionalmente molto performante e che, nel caso in cui n sia composto, esista certamente un “testimone” a di tale proprietà, consente di utilizzare in pratica il metodo di Miller-Rabin per verificare con “alta” probabilità che un intero è primo. Maggiori dettagli si trovano, ad esempio, nel §3.8 di [4].
Abbiamo quindi uno strumento, basato sulle congruenze, che è affidabile e veloce e che consente di “ridurre” la probabilità che un intero possa essere composto. Vogliamo anche fare notare che il recente risultato (2002) di Agrawal-Kayal-Saxena, che dimostra la possibilità di verificare la primalità di un intero con una quantità di calcoli dipendente in modo polinomiale dal numero di cifre di n, è anch'esso basato sulla verifica di una serie di congruenze (sebbene esse siano effettuate nell'anello dei polinomi a coefficienti interi Z[x] e non in Z).
In conclusione, al giorno d'oggi esistono algoritmi che consentono di provare la primalità di un intero n eseguendo un numero di calcoli essenzialmente del tipo (log n)6 operazioni effettuate sui bit e, da un punto di vista pratico, le loro implementazioni consentono di “produrre” in pochi secondi, utilizzando hardware facilmente accessibile in commercio, numeri primi di forma generale (si veda il paragrafo successivo) aventi 400-500 cifre decimali (ossia di grandezza più che sufficiente per le attuali applicazioni).

Marin Mersenne

Ben diversa è la situazione per gli algoritmi di fattorizzazione. È immediato osservare che, provando a dividere un intero n per tutti gli interi minori o uguali di √n, si ottiene un algoritmo che determina un fattore di n eseguendo un numero di calcoli che, nel caso peggiore, è circa √n operazioni effettuate sui bit; ossia effettua un calcolo estremamente più oneroso di quelli relativi alla primalità.

Sebbene esistano algoritmi molto più sofisticati della divisione per tentativi sopra descritta, il problema della fattorizzazione sembra essere computazionalmente più “difficile” della primalità. Infatti l'algoritmo di fattorizzazione più efficiente noto al giorno d'oggi (il Crivello dei Campi di Numeri di Pollard e Lenstra) per determinare un fattore di n effettua un numero di calcoli che è circa pari a

operazioni effettuate sui bit. Chiaramente anche questa verifica è estremamente più onerosa di quella relativa alla primalità.
Per esemplificare la velocità con cui cresce la funzione esponenziale ricorriamo al seguente esempio. Prendiamo un foglio di carta da 0,1 mm e cominciamo a piegarlo su se stesso in due parti uguali. Il foglio ha ora spessore doppio (0,2 mm).
Eseguiamo un'altra piegatura: il foglio ora ha spessore quadruplo rispetto all'inizio (0,4 mm). In definitiva, con ogni piegatura raddoppiamo lo spessore del foglio stesso. Orbene, se fossimo capaci di piegarlo in tal modo 42 volte, otterremmo uno spessore maggiore della distanza Terra-Luna! Infatti, dopo aver ricordato che la distanza “media” Terra-Luna è pari a 384000 km (356410 km al perigeo e 384700 km all'apogeo), è sufficiente osservare che 242=4398046511104 e quindi lo spessore ottenuto è pari a 4398046511104 decimillimetri ossia 439804, 6511104 km.
È chiaro quindi che il “costo computazionale” della fattorizzazione è notevolmente maggiore rispetto a quello della primalità. È proprio su questa notevole differenza di “costo computazionale” che si fonda la crittografia a chiave pubblica: verrà sfruttata la capacità di generare primi per costruire un metodo crittografico efficiente e facilmente usabile mentre la difficoltà di violare tale sistema verrà fatta dipendere dalla “alta onerosità computazionale” di determinare un fattore di un intero.
Si faccia attenzione che queste affermazioni sono corrette nel caso si cerchi di fattorizzare un intero di forma “generale” ossia per cui non sia nota alcuna struttura. Ad esempio se è noto che l'intero n ha almeno un fattore primo p “piccolo” (avente ordine di grandezza del tipo logAn, A>0 fissato) l'algoritmo di divisione per tentativi determina tale p effettuando un numero di calcoli sui bit che è polinomiale sul numero di cifre di n; oppure se n è il prodotto di esattamente due fattori primi p e q entrambi “quasi” uguali a √n una strategia efficiente è quella di cercare di scrivere n=X2-Y2=(X-Y)(X+Y) perché in tal caso Y sarà piccolo e verificando quando n+Y2 è un quadrato perfetto si svolgono all'incirca Y radici quadrate di numeri aventi essenzialmente la stessa grandezza di n.
Quindi quello che sappiamo è che non siamo in grado di risolvere il caso peggiore della fattorizzazione in modo efficiente e che esistono casi particolari in cui essa è risolubile in maniera estremamente performante. Nelle applicazioni, bisognerà quindi cercare di “stare lontani” dai casi particolari in cui è noto che la fattorizzazione è efficiente per non rischiare di compromettere, ad esempio, la sicurezza di un metodo crittografico. Concretamente, non è opportuno usare i numeri primi di Mersenne (ne parliamo nel §2) come fattori della chiave pubblica n in RSA perché questi hanno una forma troppo speciale e sono di dominio pubblico. Abbiamo discusso tutte queste cose in dettaglio in [4], ma consigliamo di approfondire l'argomento consultando il libro di Crandall & Pomerance [1].
In conclusione, osserviamo che da un punto di vista psicologico, può non apparire del tutto soddisfacente sapere che un certo intero non è primo, senza conoscerne i fattori primi. Dal punto di vista pratico, invece, quando si cercano numeri primi per le applicazioni è di enorme importanza avere metodi veloci per determinare la primalità o meno, dato che non sono ancora noti metodi di fattorizzazione parimente efficienti (perlomeno nel caso generale). Le cose cambierebbero radicalmente se si scoprisse un algoritmo di fattorizzazione competitivo con i criteri di primalità, ma questo non ci sembra molto probabile sebbene esistano risultati in tal senso che però fanno uso di un metodo di computazione (il cosiddetto “computer quantistico”) che, al momento, non pare essere di prossima realizzazione.