Test di Miller-Rabin

Il test di primalità di Miller-Rabin è un test di primalità probabilistico (appartenente alla categoria degli algoritmi Monte Carlo). La sua versione originale, ideata da Gary Miller nel 1976, è deterministica, ma la sua correttezza dipende dall'ipotesi di Riemann generalizzata, un'importante congettura matematica tuttora aperta.

L'algoritmo è stato modificato nel 1980 da Michael Rabin per diventare un algoritmo probabilistico in tempo polinomiale, simile al test di Fermat e al test di Solovay-Strassen. L'algoritmo determina in modo estremamente efficiente se un dato numero sia composto; di contro, non fornisce una dimostrazione rigorosa della primalità di un numero, ma stabilisce con un margine di certezza arbitrariamente alto se esso sia un "probabile primo".

Fondamenti matematici

Analogamente ai test di Fermat e Solovay-Strassen, il test di Miller-Rabin si basa su specifiche proprietà algebriche dell'aritmetica modulare che risultano sempre vere per i numeri primi. In particolare, sfrutta il piccolo teorema di Fermat e le proprietà delle radici quadrate dell'unità.

Se $p$ è un numero primo, valgono due regole fondamentali:

1. Per il piccolo teorema di Fermat, per ogni intero $a$ non divisibile per $p$ si ha: $a^{p-1}\equiv 1{\pmod {p}}$.
2. Le uniche soluzioni dell'equazione $x^{2}\equiv 1{\pmod {p}}$ sono $x\equiv 1{\pmod {p}}$ e $x\equiv -1{\pmod {p}}$. Questo deriva dal fatto che $x^{2}-1=(x-1)(x+1)\equiv 0{\pmod {p}}$; per il lemma di Euclide, essendo $p$ primo, deve dividere necessariamente uno dei due fattori.

La fattorizzazione fondamentale

Sia $n>2$ un numero dispari (candidato a essere primo). Possiamo sempre scrivere il numero pari $n-1$ estraendo tutte le potenze di 2, ossia nella forma:

$n-1=2^{s}\cdot d$

dove $s$ è un intero positivo e $d$ è un numero dispari.

Presa una base $a$ casuale nell'intervallo $2\leq a\leq n-2$, possiamo sfruttare i prodotti notevoli per riscrivere l'espressione del piccolo teorema di Fermat $a^{n-1}-1$ mediante fattorizzazione progressiva della differenza di quadrati:

$a^{n-1}-1=a^{2^{s}d}-1=(a^{2^{s-1}d}+1)(a^{2^{s-1}d}-1).$

Reiterando la scomposizione per $s$ volte, otteniamo la seguente espressione:

$a^{n-1}-1=(a^{2^{s-1}d}+1)(a^{2^{s-2}d}+1)\cdots (a^{2d}+1)(a^{d}+1)(a^{d}-1).$

Se $n$ è un numero primo, affinché il prodotto di questi fattori sia congruo a zero modulo $n$, per la legge di annullamento del prodotto (valida nel campo o dominio d'integrità dei resti modulo un primo) almeno uno di questi fattori deve essere un multiplo di $n$.

Da questo si deduce che, se $n$ è primo, per ogni base $a$ coprima con $n$ deve valere necessariamente almeno una delle seguenti condizioni:

• $a^{d}\equiv 1{\pmod {n}}$;
• $a^{2^{r}d}\equiv -1{\pmod {n}}$ per qualche $r$ tale che $0\leq r<s$.

Un numero $n$ che soddisfa queste condizioni per una determinata base $a$ prende il nome di pseudoprimo forte in base $a$.

Testimoni e forti bugiardi

La sequenza delle $s+1$ quadrature $\{a^{d},a^{2d},a^{4d},\dots ,a^{2^{s}d}\}$ calcolate modulo $n$ permette di scoprire se $n$ è composto.

• Se la sequenza non inizia con $1$ e non contiene mai $-1$, allora $n$ non rispetta le proprietà dei numeri primi. La base $a$ che rivela la scomposizione prende il nome di testimone di Miller-Rabin per la non-primalità di $n$.
• Se $n$ è composto ma passa comunque il test per una determinata base $a$, la base $a$ viene definita falso testimone o forte bugiardo.

Nessun numero composto (nemmeno i temibili numeri di Carmichael) è uno pseudoprimo forte per tutte le basi. L'insieme dei "forti bugiardi" di un numero composto $n$ forma un sottogruppo proprio del gruppo moltiplicativo $\mathbb {Z} _{n}^{*}$. Per il Teorema di Lagrange, l'ordine di un sottogruppo proprio deve dividere l'ordine del gruppo, il che implica che i bugiardi possono essere al massimo la metà degli elementi totali. In realtà, Rabin ha dimostrato un limite ancora più stringente: i forti bugiardi sono sempre meno di 1/4 delle basi possibili.

L'algoritmo

L'algoritmo consiste nell'isolare la parte dispari $d$ di $n-1$ e testare una o più basi $a$ casuali eseguendo quadrature successive.

Pseudocodice

Input: n > 3 (un intero dispari da testare), k (numero di iterazioni per aumentare la precisione)
Output: "Composto" oppure "Probabilmente primo"

Scrivi n - 1 come 2^s * d, con d dispari, dividendo progressivamente per 2.

Ciclo per k iterazioni:
    Campiona a uniformemente a caso in [2, n - 2]
    
    x = a^d mod n
    Se x = 1 oppure x = n - 1:
        Passa alla prossima iterazione (il test per questa base è superato, a è un possibile bugiardo)
    
    ciclo_interno_superato = Falso
    Ripeti s - 1 volte:
        x = x^2 mod n
        Se x = n - 1:
            ciclo_interno_superato = Vero
            Interrompi il ciclo interno
            
    Se ciclo_interno_superato = Falso:
        Restituisci "Composto" (a è un testimone)

Restituisci "Probabilmente primo"

Si nota che l'algoritmo non fa uso di grandi numeri in memoria; ogni valore $x$ viene calcolato sfruttando l'elevamento a potenza modulare, mantenendo i risultati sempre minori di $n$.

Complessità e affidabilità

Il test di Miller-Rabin è estremamente efficiente. Se $n$ è il numero da testare, rappresentabile con $\log n$ bit, le operazioni di elevamento a potenza modulare e quadratura richiedono un tempo pari a $O((\log n)^{3})$ usando moltiplicazioni standard.

Probabilità di errore

A differenza del test di Fermat, il test di Miller-Rabin non soffre del problema dei numeri di Carmichael. Per qualsiasi numero dispari composto $n$, la probabilità che esso passi il test per una singola base casuale è minore o uguale a ${\frac {1}{4}}$.

Ripetendo il test per $k$ basi generate in modo indipendente, la probabilità che un numero composto venga erroneamente classificato come "probabilmente primo" è limitata da:

$P({\text{errore}})\leq {\frac {1}{4^{k}}}.$

Tale probabilità decresce in modo esponenziale, permettendo di raggiungere una certezza virtuale (es. errore $10^{-60}$ con $k=100$) in pochissimi millisecondi di calcolo.

Versione deterministica

Se l'ipotesi di Riemann generalizzata (GRH) risultasse vera, sarebbe possibile convertire il test di Miller-Rabin da un test probabilistico a un test deterministico rigoroso. Secondo la GRH, per dimostrare la primalità o composizione di $n$, sarebbe sufficiente controllare tutte le basi $a$ tali che:

$a\leq 2(\ln n)^{2}.$

In questo caso, nessun numero composto potrebbe sfuggeire a tutti i testimoni in quell'intervallo. L'algoritmo risulterebbe eseguibile in tempo strettamente polinomiale, come dimostrato originariamente da Gary Miller nel 1976.

Test con piccoli insiemi di basi

Nel caso della programmazione pratica, se $n$ rientra nei tipici interi a 32 o 64 bit dei linguaggi di programmazione, non è necessario usare basi casuali. Un insieme preselezionato di poche basi piccole garantisce l'identificazione di tutti i numeri composti fino a un massimo precalcolato:

• Se $n<4.759.123.141$ (circa $4,7\times 10^{9}$, tutti i numeri a 32 bit), è sufficiente testare $a=2,7$ e $61$.
• Se $n<3.317.044.064.679.887.385.961.981$ (circa $3,3\times 10^{24}$), è sufficiente testare i primi 13 numeri primi da 2 a 41.

Voci correlate

• Numero primo
• Pseudoprimo
• Test di Fermat
• Test di Lucas-Lehmer
• Test di Wilson
• Metodo Monte Carlo
• Teorema di Eulero (aritmetica modulare)

Altri progetti

Altri progetti

• Wikibooks

• Wikibooks contiene testi o manuali sul Test di Miller-Rabin

Collegamenti esterni

• (EN) Miller-Rabin test, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Rabin-Miller Strong Pseudoprime Test, su MathWorld, Wolfram Research.