Test di Miller-Rabin

La fattorizzazione fondamentale

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

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

dove ${\displaystyle s}$ è un intero positivo e ${\displaystyle d}$ è un numero dispari.

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

${\displaystyle 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 ${\displaystyle s}$ volte, otteniamo la seguente espressione:

${\displaystyle 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 ${\displaystyle n}$ è un numero primo, affinché il prodotto di questi fattori sia congruo a zero modulo ${\displaystyle 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 ${\displaystyle n}$.

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

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

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

Testimoni e forti bugiardi

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

• Se la sequenza non inizia con ${\displaystyle 1}$ e non contiene mai ${\displaystyle -1}$, allora ${\displaystyle n}$ non rispetta le proprietà dei numeri primi. La base ${\displaystyle a}$ che rivela la scomposizione prende il nome di testimone di Miller-Rabin per la non-primalità di ${\displaystyle n}$.
• Se ${\displaystyle n}$ è composto ma passa comunque il test per una determinata base ${\displaystyle a}$, la base ${\displaystyle 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 ${\displaystyle n}$ forma un sottogruppo proprio del gruppo moltiplicativo ${\displaystyle \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.

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 ${\displaystyle x}$ viene calcolato sfruttando l'elevamento a potenza modulare, mantenendo i risultati sempre minori di ${\displaystyle n}$.

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 ${\displaystyle n}$, la probabilità che esso passi il test per una singola base casuale è minore o uguale a ${\displaystyle {\frac {1}{4}}}$.

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

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

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