Il Problema della Primalità – I Test Probabilistici di Fermat e di Miller-Rabin

In questo articolo studieremo il problema di determinare se un numero naturale è primo oppure composto. Un numero primo è un numero naturale maggiore di \(1\) che ha come soli divisori il numero \(1\) e se stesso. In alcuni casi si può escludere subito la primalità di un numero naturale. Ad esempio i numeri naturali pari, ad eccezione del numero \(2\), non sono primi. Se la cifra finale è \(5\) allora il numero è divisibile per \(5\). Se la somma delle cifre è un multiplo di \(3\) allora il numero è divisibile per \(3\).
Tuttavia, tranne che nei casi banali, per determinare la primalità di un numero intero positivo con un numero grande di cifre è necessario eseguire degli algoritmi, che mediante iterazioni di operazioni aritmetiche e algebriche permettano di escludere la presenza di divisori propri, cioè diversi da \(1\) e da se stesso. All’aumentare del numero delle cifre la soluzione del problema diventa complessa e infine impossibile, anche con i computer più potenti a disposizione.
In questo articolo descriveremo la complessità computazionale di alcuni algoritmi, chiamati anche test di primalità, e analizzeremo in dettaglio gli algoritmi probabilistici di Fermat e di Miller-Rabin.
Lo sviluppo di test di primalità ha una grande importanza non solo teorica ma anche pratica, in particolare per le sue implicazioni nella sicurezza dei sistemi di crittografia a chiave pubblica. Ad esempio, uno dei passi dell’algoritmo RSA (Rivest–Shamir–Adleman) richiede di generare dei numeri primi molto grandi, con centinaia di cifre decimali (vedi articolo su questo sito).

1) Due problemi fondamentali: primalità e fattorizzazione

Indichiamo con \(\mathbb{Z}=\{\cdots,-3,-2-1-1,0,1,2,3,\cdots\}\) l’insieme degli interi e con \(\mathbb{Z}^{+}=\{1,2,3,\cdots \}\) l’insieme degli interi positivi. L’insieme dei numeri naturali \(\mathbb{N}=\{0,1,2,3,\cdots\}\) è costituito dagli interi non negativi.
Negli ‘Elementi’ di Euclide viene dimostrato che esistono infiniti numeri primi. La serie iniziale dei numeri primi è la seguente:

\[ 2,3,5,7,11,13,17,19,23, \cdots \]

I numeri primi sono considerati i mattoni della matematica. Questo è dovuto al teorema fondamentale dell’aritmetica, secondo il quale ogni numero naturale \(n\) può essere rappresentato in modo univoco come prodotto finito di potenze di primi distinti:

\[ n= p_{1}^{a_{1}}p_{2}^{a_{2}} \cdots p_{k}^{a_{k}} =\prod\limits_{i=1}^{k}p_{i}^{a_{i}} \]

La decomposizione è unica, a parte l’ordine dei fattori. Due problemi di fondamentale importanza sono i seguenti:

• primalità: dato un intero positivo \(n\) determinare se è un numero primo;
• fattorizzazione: dato un intero positivo \(n\) trovare la sua scomposizione in fattori primi.

La primalità e la fattorizzazione sono due problemi molto interessanti in primo luogo dal punto di vista teorico, come espresso in particolare dal grande matematico Gauss:

“Il problema di separare i primi dai composti e di decomporre i secondi nei loro fattori primi è conosciuto essere uno dei più importanti e utili in Matematica. La dignità stessa della scienza sembra richiedere di esplorare ogni possibile mezzo per la soluzione di un problema così elegante e famoso.”

Gauss (Disquisitiones Aritmeticae, 1801)

Tuttavia questi problemi hanno assunto una importanza fondamentale anche dal punto di vista pratico nella moderna società dell’informazione. Infatti la teoria dei numeri primi è alla base di molti sistemi di crittografia, indispensabili per garantire la sicurezza, riservatezza e integrità delle informazioni trasmesse sulle reti di computer, in particolare su internet. Ad esempio la sicurezza dell’algoritmo RSA dipende dalla difficoltà di trovare algoritmi efficienti, in grado di determinare la fattorizzazione di numeri interi molto grandi.
I due problemi della primalità e della fattorizzazione di un numero naturale sono per loro natura diversi. Naturalmente è più facile stabilire se un numero è primo, piuttosto che trovarne tutti i suoi fattori primi.
Ad oggi sono stati sviluppati sofisticati algoritmi, sia deterministici sia probabilistici, per risolvere questi problemi. Comunque, tranne casi particolari, anche utilizzando i supercomputer oggi a disposizione non è possibile fattorizzare numeri interi aventi più di qualche centinaia di cifre decimali.
In questo articolo studieremo alcuni degli algoritmi utilizzati per determinare se un numero intero positivo è primo, valutando anche la relativa complessità computazionale. In un articolo successivo studieremo il problema e gli algoritmi utilizzati per determinare la fattorizzazione in numeri primi di un intero positivo composto.

2) Algoritmi e complessità

Un algoritmo è una sequenza di istruzioni che devono essere eseguite per risolvere un problema, o in generale per svolgere una certa attività. Un algoritmo può anche essere eseguito manualmente, come ad esempio una ricetta per preparare un dolce. Tuttavia, tranne nei casi più semplici, per risolvere i problemi matematici si utilizzano i computer. Per questo le istruzioni dell’algoritmo devono essere tradotte in un programma informatico, tramite un opportuno linguaggio di programmazione.
In generale un algoritmo ha dei dati in ingresso (input) e fornisce dei risultati in uscita (output). La complessità di un algoritmo è una funzione che dipende dalle dimensioni dell’input e rappresenta il costo necessario per eseguire l’algoritmo. Esistono due tipi di complessità:

• complessità temporale: la quantità di tempo necessaria per eseguire il programma;
• complessità spaziale: l’utilizzo delle risorse, in particolare la quantità di memoria necessaria al programma per la sua esecuzione completa.

Nel seguito, se non specificato diversamente, quando parliamo di complessità intendiamo complessità temporale.
Per calcolare la complessità si utilizza l’analisi asintotica, che in matematica studia l’andamento delle funzioni. Per questo è utile ricordare alcuni concetti e definizioni.

2.1) Analisi asintotica delle funzioni

Lo studio del comportamento asintotico delle funzioni ha una importanza fondamentale in molti settori della matematica e nello studio della complessità degli algoritmi. Nella teoria dei numeri molte funzioni aritmetiche hanno un comportamento irregolare. Ad esempio la funzione \(d(n)\), che conta il numero dei divisori di un intero \(n\), assume il valore \(2\) su tutti i numeri primi; d’altra parte può assumere valori grandi a piacere, ad esempio \(d(2^{k})=k+1\), al tendere di \(k\) all’infinito. La funzione quindi non tende ad un valore definito al crescere di \(n\), ma oscilla indefinitivamente fra il valore minimo e valori grandi a piacere. Anche altre funzioni aritmetiche come la somma dei divisori \(\sigma(n)\) o la funzione di Eulero \(\varphi(n)\) hanno un comportamento irregolare.
In molti casi quindi è impossibile descrivere esattamente il comportamento di una funzione aritmetica \(f(n)\) per grandi valori di \(n\). Spesso è più utile studiare il comportamento della somma parziale

\[ S(n)= \sum\limits_{k=1}^{n}f(k) \]

oppure della media aritmetica

\[ S(n)=\frac{1}{n} \sum\limits_{k=1}^{n}f(k) \]

I simboli di Landau
Introduciamo ora alcuni simboli speciali, proposti da Landau, Bachmann, Vinogradov e altri, per descrivere il comportamento asintotico delle funzioni.
Nel definire i simboli di Landau ci limitiamo alle funzioni aritmetiche, definite sul dominio dei numeri naturali. Le definizioni possono essere estese in modo ovvio a funzioni definite sui numeri reali.
Sia \(g(n)\) definita sugli interi e a valori reali positivi. La notazione

\[ f(n) = O(g(n)) \]

significa che esiste una costante positiva \(K > 0\) tale che

\[ |f(n)| \le K g(n) \ , \quad n \ge n_{0} \]

dove \(n_{0}\) è un numero reale opportuno.
In realtà sarebbe più esatto scrivere \(f(n) \in O(g(n))\), cioè la funzione \(f(n)\) appartiene all’insieme \(O(g(n))\) delle funzioni limitate dalla \(g(n)\).
La notazione \(\Theta(n)\):

\[ f(n) = \Theta(g(n)) \]

indica che esistono due costanti positive \(c_{1},c_{2}\) tali che

\[ c_{1}g(n) \le f(n) \le c_{2} g(n) \]

Possiamo dire che il simbolo \(O(n)\) indica un limite superiore per la complessità, mentre il simbolo \(\Theta(n)\) indica un limite esatto.
È utile anche il simbolo \(o(n)\):

\[ f(n) = o(g(n)) \]

il quale indica che

\[ \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 \]

cioè \(g(n)\) cresce molto più velocemente di \(f(n)\) quanto \(n \to \infty\).

Esempio 2.1

\[ \begin{array}{l} f(n)= n^{3}+ 100n^{2}+ 2000 =O(n^{3}) \\ \sin n = O(1) \\ \dfrac{n}{n+1} = 1 + O\left(\dfrac{1}{n}\right) \\ \varphi(n) = O(n) \ , \quad \text{funzione di Eulero}\\ d(n) \le 2\sqrt{n} =O(\sqrt{n}) \ , \quad \text{numero divisori} \end{array} \]

Esercizio 2.1
Dimostrare che la relazione \( \in O(.)\) è riflessiva e transitiva. Cioè

\[ \begin{array}{l} f(n)= O(f(n)) \\ f(n)=O(g(n)) \text{ e }g(n)=O(h(n)) \implies f(n)=O(h(n)) \end{array} \]

Esercizio 2.2 – Regola del massimo
Date due funzioni \(f,g: \mathbb{N} \to [0,\infty]\) dimostrare che

\[ O(f(n)+g(n))= O(\max(f(n),g(n))) \]

Esempio 2.2

\[ O(n^{4}+ n^{2}+ n^{3}\ln n )=O(\max(n^{4},n^{2},n^{3}\ln n)) = O(n^{4}) \]

Per determinare la relazione di ordine di grandezza fra due funzioni è spesso utile utilizzare il concetto di limite. Vale il seguente teorema:

Teorema 2.1

\[ \begin{array}{l} \lim \dfrac{f(n)}{g(n)}=L \gt 0 \implies f(n)=O(g(n)) \text{ e } g(n)=O(f(n)) \\ \lim \dfrac{f(n)}{g(n)}=0 \implies f(n)=O(g(n)) \text{ ma } g(n)\notin O(f(n)) \\ \lim \dfrac{f(n)}{g(n)}=\infty \implies f(n)\notin O(g(n)) \text{ ma } g(n)= O(f(n)) \\ \end{array} \]

Esercizio 2.3
Dimostrare che \(\ln n =O(\sqrt[3]{n})\), utilizzando il teorema precedente e la regola di de l’Hopital.

Esercizio 2.4
Verificare la seguente scala della complessità, dal valore maggiore al minore.

• \(O(n!)\) – complessità fattoriale
• \(O(k^{n})\) – complessità esponenziale (\(k \gt 0\))
• \(O(n^{k})\) – complessità polinomiale (\(k \gt 0)\)
• \(O(n^{2})\) – complessità quadratica
• \(O(n \ln n)\) – complessità semilineare
• \(O(n)\) – complessità lineare
• \(O(\ln n)\) – complessità logaritmica
• \(O(1)\) – complessità costante

2.2) Complessità temporale di un algoritmo

Il calcolo della complessità temporale comporta l’analisi dell’algoritmo per determinare il numero di operazioni che esegue e il tempo impiegato per ciascuna operazione. Una volta fatto questo, la complessità temporale può essere calcolata sommando il tempo impiegato per eseguire tutte le operazioni.
Per calcolare la complessità di un algoritmo introduciamo una funzione \(T(n)\), dove \(n\) è la dimensione dell’input. In genere la funzione \(T(n)\) conta il numero delle istruzioni elementari eseguite dal programma.
Lo studio del comportamento asintotico della funzione \(T(n)\) permette di valutare la complessità computazionale.
Il tempo impiegato da un algoritmo dipende in generale dal tipo e dalle dimensioni dell’input. Si distinguono \(3\) casi possibili:

• caso migliore (best case): il tempo minimo richiesto per l’esecuzione del programma;
• caso medio (average case) – il tempo medio richiesto per l’esecuzione del programma;
• caso peggiore (worst case) – il tempo massimo richiesto per l’esecuzione del programma.

Molte volte conviene analizzare la prestazione di un algoritmo nel caso peggiore, per ogni dimensione dell’input. Questo permette di avere la certezza che l’algoritmo non richiederà un tempo maggiore per completare l’esecuzione.

Complessità polinomiale
Un algoritmo ha complessità polinomiale se il tempo di esecuzione \(T(n)\) nel caso peggiore è limitato da un polinomio \(P(n)\), per \(n\) abbastanza grande.
Esempio di complessità polinomiale sono \(T(n)=O( n^{2} + \ln n)\) oppure \(T(n)=O(n \ln n)\).

Complessità esponenziale
Un algoritmo ha complessità esponenziale se il tempo di esecuzione \(T(n)\) cresce come una funzione esponenziale dell’input.
Nel caso di complessità esponenziale la variabile \(n\) sta nell’esponente. Ad esempio una complessità dell’ordine \(T(n)=O(2^{n})\).
Gli algoritmi con complessità esponenziale sono inefficienti, in quanto il tempo di esecuzione cresce molto più velocemente rispetto all’aumento delle dimensioni del problema.
I problemi di tipo polinomiale, indicati come problemi di tipo P, sono problemi che possono essere risolti con un tempo polinomiale.
I problemi non deterministici di tipo polinomiale, indicati come problemi di tipo NP, sono problemi la cui soluzione può essere verificata in tempo polinomiale, anche se non si dipone di un algoritmo polinomiale per risolverlo.
Un esempio di problema di tipo NP è il problema della fattorizzazione di un intero in numeri primi. Possiamo verificare se un intero divide un altro intero in un tempo polinomiale, ma non esiste un algoritmo in grado di fattorizzare un intero in un tempo polinomiale.

2.3) Algoritmi deterministici e probabilistici

Un algoritmo deterministico è un algoritmo il cui risultato dipende dai dati di input, e non è presente alcun elemento di casualità. Può essere rappresentato come una funzione

\[ AlgDet: X \to Y \]

Applicando la funzione \(\text{AlgDet}\) allo stesso input \(x\) otteniamo sempre lo stesso valore di output \(y\).
Un esempio classico è l’algoritmo di Euclide per il calcolo del massimo comune divisore di due interi.
Un algoritmo probabilistico è un algoritmo il cui risultato dipende in una certa misura da eventi casuali. In pratica l’algoritmo utilizza numeri pseudo-casuali (vedi articolo) che determinano la logica delle scelte effettuate. Applicando lo stesso input \(x\) due volte possiamo ottenere risultati diversi. Ci sono due tipi principali di algoritmi probabilistici:

• algoritmi Monte Carlo: possono dare come risultato finale una risposta che non è corretta;
• algoritmi Las Vegas: garantiscono una risposta corretta quando terminano l’esecuzione, tuttavia non c’è garanzia che riescano a terminare l’esecuzione in un tempo prestabilito finito.

Mentre negli algoritmi Monte Carlo il rischio è contenuto nel risultato di output, negli algoritmi Las Vegas il rischio è legato alle risorse utilizzate per i calcoli.
Negli algoritmi Las Vegas il tempo di esecuzione (e quindi le risorse utilizzate) è una variabile aleatoria. Il costo di esecuzione e l’utilizzo delle risorse può essere talmente elevato da non permettere di completare l’esecuzione, e quindi di dare una soluzione in un tempo prestabilito.
Un algoritmo Monte Carlo fornisce delle risposte in base a certe distribuzioni di probabilità. In base alle scelte casuali effettuate può produrre una soluzione che è corretta con un alto grado di probabilità, ma non con certezza.
Fissato un numero reale \(0 \lt p \lt 1\), un algoritmo Monte Carlo si dice corretto al grado \(p\) se fornisce una risposta corretta con probabilità maggiore od uguale a \(p\), in qualunque simulazione. In alcuni casi il valore di \(p\) può dipendere dalle dimensioni dell’input.

3) Complessità degli algoritmi della teoria dei numeri

Molti algoritmi utilizzati nella teoria dei numeri hanno in input dei numeri interi e vengono eseguiti tramite computer, che utilizzano il sistema binario per rappresentare i numeri. La dimensione dell’input viene quindi calcolata mediante il numero dei bit necessari per rappresentare un intero nel sistema binario.
Ricordiamo che per rappresentare un numero intero positivo \(n\) nel sistema binario occorrono \([\log_{2} n] +1\) bit. Ad esempio per il numero decimale \(201\) servono \(8\) cifre binarie, in quanto \(\log_{2}201 \approx 7,651\). La codifica binaria è infatti \(201_{10}= 11001001_{2}\).

Esercizio 3.1
Siano dati due interi \(n,m\). Il numero di bit nella rappresentazione binaria è rispettivamente \([\log_{2}(n)]+1\) e \([\log_{2}(m)]+1\).
Dimostrare che la complessità temporale per le operazioni binarie di addizione o sottrazione è

\[ \begin{array}{l} T(n \pm m)= O(\log_{2}n + \log_{2}m)=O(\max(\log_{2}n,\log_{2}m)) \end{array} \]

Suggerimento
L’addizione viene effettuata come nel sistema decimale; si sommano le cifre binarie corrispondenti e si gestisce il riporto. La sottrazione può essere effettuata calcolando prima il complemento a due del secondo operando e quindi facendo la somma.

Esercizio 3.2
Siano dati due interi \(n,m\). Dimostrare che la complessità temporale per le operazioni binarie di moltiplicazione e divisione è

\[ \begin{array}{l} T(n \cdot m)= O(\log_{2}n \cdot \log_{2}m) \end{array} \]

Nota
Ricordiamo che, cambiando la base, il valore della funzione logaritmo nella nuova base è uguale al vecchio moltiplicato per un valore costante:

\[ \log_{a}x = \frac{\log_{b}x}{\log_{b}a} \]

La moltiplicazione per un fattore costante non cambia il valore della complessità, quindi nella valutazione della complessità viene spesso utilizzato il logaritmo naturale \(\ln x= \log_{e}x \), che ha come base la costante di Eulero \( e \approx 2,718\).

3.1) Algoritmo di esponenziazione modulare veloce

Un problema frequente in molte applicazioni, come la teoria dei numeri e la crittografia, è il seguente: dato un intero \(a\) calcolare il numero intero \(b\) tale che

\[ a^{n} \equiv b \pmod m \ , \quad n \ge 0 \quad \text{ e } \quad 0 \le a \lt m \]

dove in genere \(m,n\) sono numeri interi molto grandi.
Un metodo elementare consiste nel moltiplicare il numero \(a\) per se stesso \(n-1\) volte e quindi dividere il risultato per il modulo \(m\). Tuttavia nel caso di numeri molto grandi questo approccio non è praticabile per vari motivi. Il principale è che il numero delle moltiplicazioni da effettuare richiederebbe dei tempi proibitivi, anche con i computer più potenti.

Il metodo dei quadrati ripetuti
Vediamo ora un algoritmo più efficiente. L’idea base del metodo è che le potenze \(q_{i}=a^{2^{i}},\ i=0,1,\cdots,t\) possono essere calcolate mediante la seguente formula ricorsiva:

\[ \begin{array}{l} q_{0}= a \pmod{m}\\ q_{i}=q_{i-1}^{2} \pmod{m} \end{array} \]

Esempio 3.1
Supponiamo di dover calcolare \(a^{32}\). Il metodo ingenuo di calcolo

\[ a \cdot a \cdot a \cdots a \]

richiede \(31\) moltiplicazioni.
Un metodo più efficiente consiste nel calcolare

\[ a^{32} = ((((a^{2})^{2})^{2})^{2})^{2} \]

che richiede \(5\) moltiplicazioni.
Rappresentiamo ora \(n\) nel sistema binario, cioè

\[ n= n_{k-1}n_{k-2} \cdots n_{1}n_{0}= n_{0}+2n_{1}+ \cdots 2^{k-1}n_{k-1} \]

dove le cifre \(n_{i}\) assumono i valori \(0,1\).

\[ \displaystyle a^{n} = a^{n_{0}+2n_{1}+ \cdots 2^{k-1}n_{k-1}}= a^{n_{0}}a^{2n_{1}}a^{2^{2}n_{2}}\cdots a^{ 2^{k-1}n_{k-1}} \]

Quindi

\[ a^{n}\pmod m = \left( \prod_{0 \le i \lt k \\ n_{i}=1} a^{2^{i}n_{i}}\right) \pmod m \]

Esempio 3.2
Calcoliamo \(a=2^{31} \pmod {17}\). Nel sistema binario abbiamo \(31\) uguale a \(11111\), cioè \(31=1+ 2+2^{2}+ 2^{3}+2^{4}\).
Indichiamo con \(c_{i}\) i prodotti parziali. La seguente tabella descrive l’algoritmo:

\[ \begin{array}{|c|c|c|} \hline i \quad & q_{i} & n_{i} & c_{i} & \\ \hline 0 \quad & 2^{1}=2 \pmod {17} & 1 & 2 \pmod {17} = 2 & \\ \hline 1 \quad & 2^{2}=4 \pmod {17} & 1 & 2 \cdot 4 = 8 \pmod {17} & \\ \hline 2 \quad & 4^{2}=16 \pmod {17} & 1 & 8\cdot 16 \pmod {17}= 9 & \\ \hline 3 \quad & 16^{2}=1 \pmod {17} & 1 & 9\cdot 1 \pmod {17}= 9 & \\ \hline 4 \quad & 1^{2}=1 \pmod {17} & 1 & 9\cdot 1 \pmod {17}= 9 & \\ \hline \end{array} \]

Quindi abbiamo \(2^{31} \equiv 9 \pmod { 17}\).
Dall’esempio sopra riportato si vede che per calcolare \(a^{n}\) sono necessarie \(O(\ln n)\) moltiplicazioni e divisioni fra numeri minori di \(m^{2}\). Quindi vale il seguente teorema:

Teorema 3.1
La complessità temporale dell’algoritmo di esponenziazione modulare veloce è \(O((\ln n)(\ln^{2}m))\).

3.2) Operazioni elementari e tempo di esecuzione

Una operazione, come un’addizione o una moltiplicazione, può essere definita elementare se il suo tempo di esecuzione è limitato superiormente da una costante, che può dipendere dall’algoritmo di implementazione o dal computer utilizzato ma che non dipende dalle dimensioni dei numeri in gioco.
Tuttavia l’ipotesi che la moltiplicazione fra due numeri avvenga in un tempo costante non è più valida nel caso di numeri molto grandi. Se moltiplichiamo due interi, allora la complessità della moltiplicazione è una funzione, indicata con \(M(l)\), dove \(l\) è il numero dei bit dei due operandi. Se si utilizza l’algoritmo ordinario per la moltiplicazione allora \(M(l)=O(l^{2})\). Esistono tuttavia algoritmi sofisticati in grado di eseguire la moltiplicazione con maggiore efficienza.
Un esempio è l’algoritmo di moltiplicazione di Anatoly Karatsuba (1937-2028), pubblicato nel \(1962\).

Esempio 3.3 – Il metodo di Karatsuba
Illustriamo l’algoritmo di Karatsuba, supponendo di voler calcolare il prodotto \(541 \cdot 3456\).
Spezziamo ogni operando in due parti:

\[ \begin{array}{l} 541 = 10^{2}w + x \ , \quad w=05 \ , \quad x=41 \\ 3456 = 10^{2}y + z \ , \quad y=34 \ , \quad z=56 \\ \end{array} \]

Moltiplicando abbiamo

\[ \begin{array}{l} 541\cdot 3456 = (10^{2}w + x) \cdot (10^{2}y + z) = \\ 10^{4}wy + 10^{2}(wz+xy) + xz = 1869696 \end{array} \]

Con l’algoritmo elementare sono necessarie 4 moltiplicazioni.
L’idea base dell’algoritmo è che non serve calcolare \(wz\) e \(xy\), ma solo la loro somma. Infatti una volta calcolato \(wy\) e \(xz\), abbiamo

\[ \begin{array}{l} (w+x)(y+z)= wy + xz + (wz+xy) \end{array} \]

Poniamo ora

\[ \begin{array}{l} t = (w + x)(y+z)= wy + xz +(wz+xy) \\ wz+xy = t -wy -xz \end{array} \]

Con una sola moltiplicazione abbiamo tutti e tre i termini necessari per calcolare il prodotto. Facendo i calcoli abbiamo

\[ \begin{array}{l} 541 \cdot 3456 = (10^{2}w + x) \cdot (10^{2}y + z) = \\ 10^{4}wy + 10^{2}(wz+xy) + xz = \\ 10^{4}wy + 10^{2}(t-wy-xz) + xz = 1869696 \end{array} \]

Quindi abbiamo effettuato il prodotto \(541 \cdot 3456\) con tre moltiplicazioni, invece che con quattro. In realtà c’è un numero maggiore di addizioni e sottrazioni, ma per numeri molto grandi il tempo per queste operazioni è trascurabile, rispetto al tempo necessario per le moltiplicazioni.
Nel seguito, a meno che non sia specificato diversamente, considereremo esclusivamente le operazioni elementari.
Per l’analisi dettagliata del metodo di Karatsuba e altri metodi di moltiplicazione veloce vedere il testo di Knuth ^[6].

4) Metodi elementari per riconoscere i numeri primi

Descriviamo alcuni algoritmi elementari per riconoscere se un intero positivo è primo oppure composto.

4.1) Criterio delle divisioni successive

L’approccio più elementare consiste nel dividere l’intero positivo \(n\) per ogni intero \(x\), con \(2 \le x \le \sqrt{n}\). Se nessuno degli \(x\) divide \(n\) allora \(n\) è un numero primo.
Nell’algoritmo ci si può limitare a \(\sqrt{n}\) poichè è facile dimostrare che se n è un numero composto, allora ha un divisore che non supera \(\sqrt{n}\). Infatti se \(n\) è composto, allora \(n=ab \), dove \(a,b\) sono interi maggiori od uguali a \(2\), con \(a\le b\). Se fosse \(a \gt \sqrt{n}\), allora \(\sqrt{n} \lt a \le b\) e come risultato \( ab \gt n\).
La complessità temporale è \(O(\sqrt{n} )\). Per valori molto grandi di \(n\) questo metodo è impraticabile, poiché si tratta di una complessità esponenziale, rispetto alla dimensione in bit di \(n\). Infatti il numero di bit necessari per rappresentare il numero intero \(n\) è approssimativamente \(\log_{2}(n)\). Quindi la complessità espressa tramite questa misura è

\[ \sqrt{n}= 2^{(\log_{2}(n))/2} \]

Ad esempio per applicare il test ad un numero di \(512\) bit, servono approssimativamente \(2^{256}\) operazioni elementari. Un numero molto grande anche per un supercomputer.
L’algoritmo si può velocizzare dividendo solo per i numeri primi \(p \le \sqrt{n}\).
Naturalmente questo richiede un algoritmo aggiuntivo, in grado di elencare i numeri primi fino ad un certo valore. Per determinare la complessità temporale dell’algoritmo in questo caso utilizziamo la funzione \(\pi(x)\) che conta i numeri primi non maggiori di \(x\). Il valore della funzione \(\pi(x)\) può essere approssimato mediante il teorema dei numeri primi:

\[ \pi(x) \sim \frac{x}{\ln x} \]

Da cui

\[ O(\pi (\sqrt{n}))= O\left(\frac{\sqrt{n}}{\ln \sqrt{n}}\right) \]

Naturalmente bisogna aggiungere la complessità di preparare la lista dei primi inferiori ad un dato numero.

4.2) Il crivello di Eratostene

Il crivello di Eratostene è un algoritmo semplice ideato dal matematico greco Eratostene (276 – 194 a.C.) per individuare tutti i numeri primi minori di un fissato numero intero positivo \(n\). In primo luogo osserviamo che il numero \(2\) è primo (l’unico numero primo pari). Quindi eseguiamo i seguenti passi:

• scrivere la lista di tutti i numeri interi maggiori di \(1\) fino al numero \(n\) che si vuole verificare;
• togliere dalla lista tutti i multipli del primo numero (la prima volta saranno i multipli di \(2\)). Il primo numero rimasto nella lista  è un numero primo;
• ripetere il passo precedente fino a che non ci sono più multipli dei numeri primi che sono minori di \(n\).

Come nel caso precedente, anche questo algoritmo si può limitare ad eliminare i multipli minori di \(\sqrt{n}\).

Uno pseudocodice dell’algoritmo di Eratostene è il seguente:

Algoritmo di Eratostene - Trova i numeri primi <= n
Input: un intero n > 1
Output: il vettore A di dimensione n                          
for (i = 2; i <= n; i++)  {A[i] = 1}
for (i = 2; i*i <= n; i++) { 
    if (A[i] = 1) {
        for (j = i*i, j <= n; j = j+i){
           A[j] = 0
        }
    }
}

I numeri primi sono tutti gli indici i tali che A[i]=1.

Complessità dell’algoritmo di Eratostene
Si può verificare che il tempo richiesto \(T(n)\) è

\[ T(n)= \frac{n}{2}+ \frac{n}{3}+\frac{n}{5}+ + \cdots = \\ n \cdot \left(\frac{1}{2}+ \frac{1}{3}+ \frac{1}{5}+ \cdots \right) \approx n \cdot (\ln \ln (n)) \]

Per calcolare la complessità dell’algoritmo di Eratostene abbiamo utilizzato il seguente teorema di Mertens (1840-1927):

Teorema 4.1 – Mertens

\[ \sum\limits_{p \le n}{}\frac{1}{p} \sim \ln \ln n + M \ , \quad M \approx 0,261497 \]

L’algoritmo di Eratostene è semplice e facile da implementare con un programma, tuttavia per valori molto grandi di \(n\) diventa poco efficiente, anche con i computer più potenti. Per risolvere in modo soddisfacente il problema della primalità è necessario trovare un algoritmo di complessità polinomiale rispetto alla lunghezza dell’input.

4.3) Il test di Wilson

Ricordiamo anche il test di Wilson, che nonostante la sua semplicità è di scarsa utilità pratica.

Teorema 4.2 – Wilson
Dato un intero positivo \(n\), le due seguenti affermazioni sono equivalenti:

\[ \begin{array}{l} 1) \quad n \text{ è primo} \\ 2) \quad (n-1)! \equiv -1 \pmod{n} \end{array} \]

Il teorema di Wilson ha soltanto un valore teorico e non pratico. Tuttavia può essere utilizzato per ottenere un elenco di tutti i numeri primi. Infatti dal teorema di Wilson, il matematico spagnolo José de Barinaga derivò un risultato importante. Supponiamo di dividere

\[ (P-1)! : \frac{P(P-1)}{2} \]

Indichiamo con \(r(n)\) il resto della divisione. Il resto è uguale a \((P-1)\) se \(P \gt 2\) è un numero primo, altrimenti il resto è zero se \(P\) è composto. Quindi otteniamo tutti i primi dispari aumentando di una unità i resti non nulli.

Teorema 4.3 – José de Barinaga (1890-1965)
L’insieme di tutti i numeri primi dispari è il seguente:

\[ \{r(n)+1: r(n) \gt 0\} \]

Esercizio 4.1
Dimostrare che le seguenti affermazioni sono equivalenti:

\[ \begin{array}{l} 1) \quad n \text{ è composto} \\ 2) \quad (n-1)! \equiv 0 \pmod {n} \end{array} \]

Per il teorema dei numeri primi e i teoremi di Mertens e di Wilson vedere ad esempio il testo di Hardy-Wright ^[7].

5) Il test di Fermat

L’utilizzo iniziale di algoritmi probabilistici per determinare se un numero è primo può essere fatto risalire al piccolo teorema di Fermat (vedi articolo su questo sito):

\[ a^{p-1} \equiv 1 \pmod{p} \ , \quad \text{con }(a,p)=1 \]

Può anche essere enunciato nel modo seguente:

\[ a^{p} \equiv a \pmod{p} \]

È un caso particolare del seguente teorema di Eulero (vedi articolo):

\[ a^{\varphi(n)} \equiv 1 \pmod{n} \ , \quad (a,n)=1 \]

dove \(\varphi(n)\) è la funzione di Eulero, che per ogni intero positivo \(n\) conta il numero degli interi positivi, compresi fra \(1\) e \(n\), che sono primi con \(n\) stesso. In simboli:

\[ \varphi (n) = |\{x\in \mathbb{N} : 1\leq x\leq n, (x,n)=1\}| \]

Esempio 5.1

\[ \begin{array}{l} 5^{6} \equiv 1 \pmod{7} \quad \text{poiché }5^{6}=2232*7 +1 \\ 5^{10} \equiv 1 \pmod{11} \\ 6^{10} \equiv 1 \pmod{11} \end{array} \]

Esercizio 5.1
Dimostrare che se \(\varphi(n)=n-1\) allora \(n\) è primo.

L’opposto del piccolo teorema di Fermat è un criterio utile per determinare se un numero intero è composto. Infatti vale il seguente:

Teorema 5.1 – Inverso del piccolo teorema di Fermat

\[ a^{n-1} \not\equiv 1 \pmod{n} \ , \text{ con } (a,n)=1 \implies \text{ n è composto} \]

Possiamo utilizzare il piccolo teorema di Fermat nella forma inversa per identificare i numeri composti. La seguente tabella contiene alcune potenze di \(2\):

\[ \begin{array}{|c|c|c|c|c|l|} \hline n \quad & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline 2^{n-1} \pmod n \quad & 1 & 0 & 1 & 2 & 1 & 0 & 4 & 2 & 1 & 8 & 1 \\ \hline \end{array} \]

I numeri il cui risultato è diverso da 1 sono composti: 4,6,8,9,10,12.

Esercizio 5.2
Dimostrare che il numero \(117\) è composto. In particolare dimostrare la seguente relazione:

\[ 2^{117} \equiv 44 \pmod{117} \]

Definizione 5.1
Un numero intero \(1 \le a \lt n\) viene chiamato un F-witness (testimone di Fermat) rispetto al numero \(n\) se \(a^{n-1} \not \equiv 1 \pmod{n}\).

Definizione 5.2
Sia \(n\) un numero composto dispari. Un numero intero \(1 \le a \lt n\) viene chiamato un F-liar (falso testimone) rispetto al numero \(n\) se \(a^{n-1} \equiv 1 \pmod{n}\).

Esempio 5.2
Prendendo \(a=2\), si può verificare che \(2\) è un F-witness per tutti i numeri composti minori od uguali a \(340\). Tuttavia è facile verificare che

\[ 2^{340} \equiv 1 \pmod{341} \]

Il numero \(341\) è composto, in quanto \(341=11 \cdot 31\). Quindi \(2\) è un F-liar per il numero \(341\).

Esercizio 5.3
Dimostrare che

\[ 3^{340} \equiv 56 \pmod{341} \]

Quindi \(3\) è un F-witness per il numero \(341\).

Esercizio 5.4
Dimostrare che \(1\) e \(n-1\) sono F-liar per ogni numero composto dispari \(n\).

5.1) Numeri pseudoprimi

Un numero intero composto \(n \ge 2\) si dice pseudoprimo (detto anche pseudoprimo di Fermat) rispetto alla base \(a \ge 2\) se risulta \(a^{n-1} \equiv 1 \pmod{n}\).
Il più piccolo pseudoprimo \(n\) rispetto alla base \(b=2\) è \(341=11 \cdot 31\). Infatti risulta \(2^{340} \equiv 1 \pmod {341}\).

Si può dimostrare il seguente teorema:

Teorema 5.2
Per ogni base \(a \gt 1\) esistono infiniti pseudoprimi rispetto alla stessa base.

Tuttavia il numero degli pseudoprimi rispetto ad una base \(a\) è molto più basso rispetto al numero dei primi. Vale il seguente teorema:

Teorema 5.3 – Erdos-Li
Il numero degli pseudoprimi rispetto ad una data base \(a \ge 2\) che sono minori o uguali ad \(x\) è \(o(\pi(x))\), quando \(x \to \infty\).

Ad esempio il numero di pseudoprimi in base \(2\) inferiori a \(25 \cdot 10^{9}\) è \(21853\), mentre il numero di primi nello stesso intervallo è dell’ordine di \(10^{9}\).

5.2) Il gruppo \(\mathbb{Z}_{n}^{*}\)

Ricordiamo che nell’anello degli interi \(\mathbb{Z}_{n}(+,\cdot)\), l’insieme degli elementi invertibili rispetto all’operazione di moltiplicazione

\[ \mathbb{Z}_{n}^{*} = \{a|1 \le a \lt n,\ (a,n)=1\} \]

è un gruppo moltiplicativo.
Un elemento \(a\) appartiene a gruppo se e solo se esiste un elemento \(b\) tale che \( a\cdot b \equiv 1 \pmod{n}\).
Il numero degli elementi di questo gruppo è dato dalla funzione di Eulero \(\varphi(n)\), che conta il numero degli interi positivi \(1 \le a \le n\) tali che \((a,n)=1\).

Esercizio 5.5
Dimostrare che se \(n \gt 1\) e \(1 \le a \lt n\) e se risulta

\[ a^{k} \equiv 1 \pmod{n} \]

per qualche \(k \ge 1\), allora \(a \in \mathbb{Z}_{n}^{*}\).

Soluzione
Considerare

\[ a^{k}= a \cdot a^{k-1}\equiv 1 \pmod{n} \]

Esercizio 5.6
Dimostrare che se risulta

\[ a^{n-1} \equiv 1 \pmod{n} \quad \forall a: 1 \le a \lt n \]

allora \(n\) è primo.
Per il teorema precedente se \(n\) è un numero composto dispari, allora esiste almeno un F-witness per \(n\).

5.3) Il test iterativo di Fermat

La base teorica per il test di Fermat è data dal seguente teorema:

Teorema 5.4
Supponiamo che \(n\) sia un numero dispari composto ed esista almeno un F-witness \(a\) in \(\mathbb{Z}_{n}^{*}\). Allora il numero dei testimoni di Fermat che \(n\) è composto è almeno \((n-1)/2\).
Più precisamente si può dimostrare che se \(n\) è composto dispari ed esiste almeno un F-witness, allora l’insieme

\[ H_{n} = \{a| 1 \le a \lt n, a^{n-1} \equiv 1 \pmod{n}\} \]

è un sottogruppo proprio di \(\mathbb{Z}_{n}^{*}\), tale che

\[ |H_{n}| \le \frac{n-2}{2} \]

In base al teorema precedente viene definito l’algoritmo di Fermat :

Input: n intero dispari > 2; 
a = random(2,3,...,n-2) 
if (power(a, n-1) % n != 1)
   then return 1  // certamente composto 
   else return 0  // probabilmente primo

In base al teorema 5.4 questo algoritmo da una risposta esatta con probabilità maggiore di \(\dfrac{1}{2}\). Infatti la probabilità che un numero scelto a caso nell’insieme \(\{2,3,\cdots, n-2\}\) appartenga all’insieme \(H_{n}-\{1,n-1\}\) è al massimo

\[ \frac{(n-2)/2 -2}{n-3} = \frac{n-6}{2n-6} \lt \frac{1}{2} \]

Naturalmente con una singola prova la probabilità che un numero composto venga scambiato per primo è elevata, fino al limite di \(\dfrac{1}{2}\). Tuttavia ripetendo il test un certo numero di volte possiamo ottenere un algoritmo molto efficiente.
Lo pseudocodice dell’algoritmo, utilizzando una sintassi simile al linguaggio C,

Input: n intero dispari > 2; 
        k numero cicli;
for (i = 1; i <= k; i++) {
    a = random(2,3,...,n-2) 
    if (power(a, n-1) % n != 1)
      then return 1  // certamente composto 
}
return 0  // probabilmente primo

Ricordiamo che il simbolo \(\text{%}\) indica il resto della divisione fra la potenza \(a^{n-1}\) e \(n\).
Scegliendo un numero di cicli \(k\) abbastanza grande, possiamo rendere piccola a piacere \(2^{-k}\) la probabilità che un numero composto venga scambiato per primo.
La complessità temporale dell’algoritmo di Fermat è

\[ T(n) = O(k \ln n) \]

dove \(k\) è il numero delle iterazioni.

5.4) Limiti dell’algoritmo di Fermat

Abbiamo visto che il numero di pseudoprimi rispetto ad una data base è abbastanza piccolo, e quindi è piccola la probabilità di scegliere un F-liar. Tuttavia esistono numeri composti che hanno un numero elevato di F-liar, alcuni addirittura hanno solo F-liar. In questi casi l’algoritmo di Fermat produce come risposta che si tratta di un numero primo con una grande probabilità, anche se è un numero composto.
Quindi in questi casi nell’algoritmo di Fermat la probabilità di errore non può essere resa inferiore ad un valore arbitrariamente piccolo, anche eseguendo un numero elevato di cicli.

6) Numeri di Carmichael

Il problema fondamentale con il metodo di Fermat è che esistono interi composti \(n\) che non hanno alcun F-witness nel campo \( \mathbb{Z}_{n}^{*}\), cioè risulta

\[ a^{n-1} \equiv 1 \pmod{n} \]

per ogni \( 1 \lt a \lt n\) tale che \((a,n)=1\). In tal caso il gruppo \(H_{n}\) coincide con il gruppo \(\mathbb{Z}_{n}^{*}\).
Gli interi positivi composti \(n\) che sono pseudoprimi rispetto ad ogni base relativamente prima con \(n\) sono chiamati numeri di Carmichael.
Il più piccolo numero di Carmichael è

\[ 561 = 3 \cdot 11 \cdot 17 \]

I primi numeri di Carmichael sono \(561, 1105, 1729, 2465,\cdots\). Per maggiori dettagli vedere enciclopedia online OEIS.
Il seguente teorema fornisce un criterio per identificare i numeri di Carmichael.

Teorema 6.1 – Korselt
Un numero composto dispari \(n \gt 2\) è un numero di Carmichael se e solo se

• n è libero da divisori quadrati
• se un primo \(p\) divide \(n\) allora \(p-1|n-1\).

Un’altra proprietà dei numeri di Carmichael è la seguente:

Teorema 6.2
Ogni numero di Carmichael \(n\) è dispari, ha almeno \(3\) fattori primi distinti e ogni fattore primo è minore di \(\sqrt{n}\). Cioè

\[ \begin{array}{l} n = p_{1}p_{2}\cdots p_{k} \ , \quad k \ge 3 \end{array} \]

dove i fattori primi \(p_{i}\) sono dispari e distinti fra loro.

Esercizio 6.1
Sia \(k\) un intero positivo. Dimostrare che se i tre numeri \(6k+1\), \(12k+1\) e \(18k+1\) sono numeri primi, allora il numero

\[ n = (6k+1)(12k+1)(18k+1) \]

è un numero di Carmichael. Per la dimostrazione utilizzare il criterio di Korselt.

Come esempio abbiamo il numero \(1729=7 \cdot 13 \cdot 19\).

Teorema 6.3 – Alford, Granville, Pomerance
Esistono infiniti numeri di Carmichael. Precisamente se indichiamo con \(C(x)\) il numero dei numeri di Carmichael minori od uguali ad \(x\), allora per \(x\) sufficientemente grande vale la seguente disuguaglianza:

\[ |C(x)| \gt x^{2/7} \ , \quad x \to \infty \]

7) I numeri pseudoprimi forti

I limiti del criterio di Fermat possono essere superati mediante una modifica al metodo.

7.1) Pseudoprimi forti in una base

Osserviamo che ogni numero dispari \(n\) può essere espresso nella forma

\[ \begin{array}{l} n= 2^{s}\cdot t + 1 \ , \quad s,t \text{ interi} , \ t \text{ dispari} \end{array} \]

Poiché \(n\) è dispari, risulta \(s \gt 0\).

Teorema 7.1
Sia \(p\) un primo dispari e \(p-1=2^{s}t\), dove t è dispari. Se \((a,p)=1\) allora

\[ \begin{cases} a^{t} \equiv 1 \pmod{p} \\ \text{ oppure} \\ \text{esiste }i, 0 \le i \lt s : a^{2^{i}t} \equiv -1 \pmod{p} \end{cases} \]

Dimostrazione
Per il teorema di Fermat \(a^{p-1} \equiv 1 \pmod{p}\). Consideriamo ora i numeri

\[ a^{t}, a^{2t},a^{4t}, \cdots, a^{2^{s-1}t},a^{2^{s}t} \]

Per il teorema di Fermat, l’ultimo numero \(a^{2^{s}t}=a^{p-1} \equiv 1 \pmod{p}\). Ogni numero della lista è il quadrato del precedente e quindi una delle seguenti due condizioni si deve verificare:

• il primo numero della lista \(a^{t} \equiv 1 \pmod{p}\);
• alcuni numeri iniziali della lista non sono congruenti ad \(1\) ma lo diventano da un certo punto in poi.

Nella seconda ipotesi deve esistere un numero \(x\) della lista tale che

\[ x \not \equiv 1 \pmod{p} \quad \text{e} \quad x^{2} \equiv 1 \pmod{p} \]

L’esercizio seguente dimostra che l’unico numero che soddisfa questa condizione è \(x \equiv -1 \pmod{p}\).

Esercizio 7.1
Sia \(x\) un intero \(1 \le x \lt p\) e \(p\) un numero primo. Dimostrare che

\[ x^{2} \equiv 1 \pmod{p} \implies x= 1 \text{ oppure } x=p-1 \]

Sia \(n = n= t\cdot 2^{s} + 1\), con \(s,t\) interi e \(t\) dispari. Indichiamo con \(B(n)\) l’insieme degli interi \((1 \le a \le n-1)\) tali che:

\[ B(n)= \begin{cases} a^{t} \equiv 1 \pmod {n} \\ \text{ oppure} \\ a^{2^{i}t} \equiv n-1 \pmod {n} \text{ per qualche }i, 0 \le i \lt s \\ \end{cases} \]

Definizione 7.1
Un intero positivo composto dispari \(n=2^{s}\cdot t + 1\), con \(t\) dispari, si dice pseudoprimo forte rispetto alla base \(a\) se \(a \in B(n)\).
Se \(n\) è dispari e \( a \not \in B(n)\), allora si dice che \(a\) è un testimone forte della non primalità, cioè indica che \(n\) è composto. Se invece \(n\) è uno pseudoprimo forte (quindi composto dispari) e \(a \in B(n)\), allora il numero \(a\) si dice falso testimone forte della primalità di \(n\).
La definizione di pseudoprimo forte dipende dalla base. Chiaramente è sempre vera nei casi banali \(a=1\) oppure \(a=n-1\).

Esercizio 7.2
Dato \(n=a^{2^{s}t}+1\), con \(t\) dispari, dimostrare la seguente identità:

\[ \begin{array}{l} a^{n-1} = (a^{2^{s-1}t}+1)(a^{2^{s-2}t}+1)\cdots (a^{t}+1)(a^{t}-1) \equiv 0 \pmod{n} \end{array} \]

Se \(n\) è un numero primo, allora divide uno dei fattori.

Esempio 7.1
Il primo pseudoprimo forte in base \(2\) è \(n=2047=23 \cdot 89\). Infatti

\[ \begin{array}{l} 2047=2\cdot 1023 +1 \\ 2^{1023} \equiv 1 \pmod{n} \end{array} \]

Esempio 7.2
Dimostrare che il numero \(n=3277\) è uno pseudoprimo forte in base 2.

Teorema 7.2
Se \(n\) è uno pseudoprimo forte nella base \(a\), allora è anche uno pseudoprimo di Fermat nella stessa base.
Non vale il viceversa.

Esercizio 7.3
Dimostrare che il numero \(1389\) è uno pseudoprimo, ma non è uno pseudoprimo forte in base 2.

Esercizio 7.4
Un falso testimone forte è anche un falso testimone di Fermat, ma non viceversa.

Esempio 7.3
Il numero \(1387= 19 \cdot 73\) è uno pseudoprimo di Fermat in base \(2\), ma non è uno pseudoprimo forte nella stessa base.

Esercizio 7.5
Dimostrare che la base \(158\) è un falso testimone forte della primalità di \(289\), cioè \(158 \in B(289)\).

8) Il test probabilistico di Miller-Rabin

Ricapitolando abbiamo i seguenti risultati:

• se \(n\) non è uno pseudoprimo forte rispetto ad una base \(a\), cioè \(a \not \in B(n)\), allora \(a\) è un testimone certo che \(n\) è composto;
• se un intero dispari \(n\) supera il test di pseudoprimo forte nella base \(a\), potrebbe essere un numero primo oppure composto;
• se un intero dispari \(n\) supera il test di pseudoprimo forte in tutte le basi possibili, allora è un numero primo.

Abbiamo visto che esistono delle basi che sono dei falsi testimoni forti. Ad esempio \(158\) è un falso testimone forte per la primalità di \(289\).
Un falso testimone forte è anche un falso testimone di Fermat, ma non vale il viceversa. La cosa positiva è che i falsi testimoni forti sono molto più rari dei falsi testimoni di Fermat. Infatti vale il seguente teorema:

Teorema 8.1
Sia \(n\) un intero composto dispari maggiore di \(9\). Allora il numero delle basi \( a \pmod{n}\) rispetto alle quali \(n\) è uno pseudoprimo forte è minore od uguale a \(\dfrac{\varphi(n)}{4}\), dove \(\varphi(n)\) è la funzione di Eulero.

Per la dimostrazione vedere il testo di Crandall ^[1].
In base al teorema precedente, se \(n\) è un numero composto almeno \(3/4\) degli interi in \([1,n-1]\) sono testimoni forti della non primalità di \(n\).

8.1) Algoritmo di Miller-Rabin

Se \(a \in B(n)\), dove \(n\) è un numero dispari, allora \(n\) si dice primo con forte probabilità, rispetto alla base \(a\).
Se \(n\) è primo allora \(|B(n)|=n-1\). Se invece \(n\) è composto dispari allora

\[ \dfrac{|B(n)|}{n-1}\le \dfrac{1}{4} \]

L’algoritmo di Miller-Rabin prevede di eseguire un ciclo di prove, scegliendo ogni volta un numero casuale \(a\) nell’intervallo \([2,n-2]\).
Se esiste un intero \(a \in [2,n-2]\) tale che \(a \not \in B(n)\) allora \(n\) è composto.
Tuttavia se scegliamo a caso \(k\) valori di \(a\) e tutti appartengono a \(B(n)\), non possiamo concludere che \(n\) è primo. In base al teorema 8.1 possiamo solo affermare che la probabilità che tutti quanti i \(k\) numeri \(a\) appartengano a \(B(n)\) è minore di \(4^{-k}\).

Pseudocodice dell’algoritmo di Miller-Rabin
Uno pseudocodice della funzione base dell’algoritmo di Miller-Rabin è il seguente:

Algoritmo MillerRabin - Test primalità di n
Input: n intero dispari > 1
Output: False (composto), True (probabilmente primo)
        
n = (2^s) * t + 1  \\ t dispari
a = Random(2,n-2)   
b = a^t modulo n 
if (b = 1 or b = n-1)  return true 

for (i = 1; i < s; i++) {
   b = b^2 mod n
   if b = n-1  return true 
   if b = 1  return false     
 }
return false  // n è composto
end

Questa funzione base viene chiamata un numero intero \(k\) di volte. Se \(n\) è composto, eseguendo \(k\) iterazioni del test la probabilità di dichiarare \(n\) probabilmente primo è al massimo uguale \(4^{-k}\).

Complessità dell’algoritmo di Miller-Rabin
Per determinare la complessità dell’algoritmo, osserviamo che \(n\) può essere rappresentato con \(\log_{2}n \) cifre binarie, e ogni moltiplicazione richiede un tempo di \(O(\log_{2}n \cdot \log_{2}n )\).
Nell’algoritmo di Miller-Rabin ogni chiamata alla funzione base comporta una esponenzazione modulare con esponente \(t\) e \(s-1\) operazioni di calcolo di quadrati modulo \(n\).
Con l’algoritmo classico l’operazione di esponenzazione ha complessità \(O(\log_{2} t)\). Osserviamo che \(\log_{2} n \gt \log_{2}(n-1)=\log_{2} (2^{s}t)=s + \log_{2}t\). Ogni calcolo di quadrato può essere assimilato ad una moltiplicazione, con complessità \(O(\log_{2}^{2}n)\). Quindi la complessità dell’algoritmo di Miller-Rabin, utilizzando i logaritmo naturale, è

\[ O(k \ln^{3}n) \ , \quad k \text{ numero di iterazioni} \]

9) Altri algoritmi di primalità

Esistono diversi altri algoritmi per determinare la primalità di un numero intero. Tra questi ricordiamo i seguenti:

9.1) Algoritmo di Solovay-Strassen

Si tratta di un algoritmo probabilistico, simile a quello di Miller-Rabin. Per comprendere l’algoritmo è necessario studiare la legge di reciprocità quadratica di Gauss e le proprietà dei simboli di Legendre e di Jacobi.
Per una descrizione del metodo di Solovay-Strassen vedere articolo su questo sito.

9.2) Algoritmo AKS

Si tratta del primo algoritmo deterministico che permette di determinare la primalità di un intero in un tempo polinomiale. Questo algoritmo è stato proposto nel \(2002\) da tre matematici indiani Manindra Agrawal, Neeraj Kayal e Nitin Saxena.

9.3) Test mediante le curve ellittiche

Una curva ellittica su un campo \(K\) è una curva definita da una equazione del seguente tipo

\[ y^{2}=x^{3}+ ax +b \ , \quad a,b \in K \]

con la condizione che risulti non nullo il discriminante della curva:

\[ \Delta = -16(4a^{3}+ 27b^{2}) \neq 0 \]

La condizione precedente assicura che la curva non ha punti singolari.
Una proprietà importante delle curve ellittiche è la possibilità di definire una operazione di addizione fra due punti della curva, ottenendo un altro punto che appartiene alla curva. In questo modo l’insieme dei punti della curva ellittica ha la struttura di gruppo algebrico.
Un algoritmo probabilistico basato sulle cure ellittiche è stato proposto nel \(1986\) da Goldwasser e Kilian.
Per questi algoritmi vedere ^[1] oppure ^[5].

Conclusione

Il problema di riconoscere i numeri primi è uno dei problemi fondamentali della teoria dei numeri. La teoria dei numeri primi nel passato era considerata una branca puramente teorica della matematica, senza alcuna applicazioni pratica. È famosa la frase del matematico inglese Hardy (1877-1947):

“If the theory of numbers could be employed for any practical and obviously honourable purpose, if it could be turned directly to the furtherance of human happiness or the relief of human suffering, as physiology and even chemistry can, then surely neither Gauss nor any other mathematician would have been so foolish as to decry or regret such applications. But science works for evil as well as for good (and particularly, of course, in times of war); and both Gauss and lesser mathematicians may be justified in rejoicing that there is one science, at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean.”

G. H. Hardy – A Mathematician Apology

Contrariamente all’opinione di Hardy, con l’avvento dei computer e delle reti di comunicazione la teoria dei numeri ha assunto un ruolo fondamentale in applicazioni critiche, come la crittografia e la trasmissione sicura delle informazioni.
Nonostante la sua natura probabilistica, il test di Miller-Rabin viene utilizzato in diversi sistemi crittografici, come il sistema RSA, per generare numeri primi con più di \(100\) cifre decimali.
In un prossimo articolo analizzeremo in dettaglio il problema della fattorizzazione degli interi, descrivendo alcuni algoritmi importanti e le relative complessità di calcolo.

---

Bibliografia

^[1]Crandall, Pomerance – Prime Numbers: a Computational Perspective (Springer)

^[2]Cormen, Leiserson, Rivest – Introduction to Algorithms (The MIT Press)

^[3]Davide Bressoud – Factorization and Primality Testing (Springer)

^[4]Leonard Eugene Dickson – History of the Theory of Numbers, Volume I: Divisibility and Primality (Dover Publications)

^[5]Neal Koblitz – A Course in Number Theory and Cryptography (Springer)

^[6]D. E. Knuth – The Art of Computer Programming (Addison-Wesley)

^[7] Hardy, Wright – An Introduction to the Theory of Numbers (Oxford University Press)