Test di Miller-Rabin
Il test di Miller-Rabin è un algoritmo probabilistico utilizzato per verificare se un numero è primo.
È particolarmente utile per numeri molto grandi, dove i metodi deterministici sono troppo lenti.
Questo test appartiene alla classe dei test probabilistici di primalità, il che significa che può identificare un numero come primo o come "probabilmente primo".
Come funziona?
Il test si basa sul piccolo teorema di Fermat: se \( p \) è un numero primo, allora per ogni intero \( a \) tale che \( 1 \leq a < p \)
$$ a^{p-1} \equiv 1 \pmod{p} $$
Tuttavia, questo criterio non è sufficiente, poiché alcuni numeri composti (detti pseudoprimi di Fermat) soddisfano comunque la relazione.
Il test di Miller-Rabin aggiunge ulteriori controlli basati sulla decomposizione di \( p-1 \) e verifica anche altre proprietà modulari.
Dato un numero dispari \( n > 3 \) da verificare:
- Scrivo il numero \( n-1 \) nella forma \( 2^s \cdot d \), dove \( d \) è dispari. Si ottiene dividendo \( n-1 \) ripetutamente per 2.
Esempio: se \( n = 25 \) scrivo \( n-1 = 24 = 2^3 \cdot 3 \). In questo caso \( s=3 \) e \( d=3 \).
- Scelgo un numero base \( a \) casualmente nell'intervallo \( 2 \leq a \leq n-2 \).
Esempio: se \( n = 25 \) devo scegliere l numero base tra \( 2 \leq a \leq 23 \).
- Calcolo \( x = a^d \mod n \).
Esempio: se \( n = 25 \), \( a=2 \), \( s=3 \) e \( d=3 \) scrivo $$ x = 2^3 \mod 25 $$
Se \( x \equiv 1 \pmod{n} \) o \( x \equiv n-1 \pmod{n} \), allora \( n \) supera il test e potrebbe essere primo. Il test termina qui.
In caso contrario, è necessario continuare il test e passare al punto successivo.Esempio: In questo esempio $ x = 2^3 \mod 25 = 8 $ non supera subito il test di primalità ma questo non basta per affermare che si tratti di un numero composto. Quindi, procedo il test considerando $ x=8 $.
- Calcolo \( x = x^2 \mod n \) e verifico:
- Se \( x \equiv n-1 \pmod{n} \), il test è superato. Il numero è probabilmente primo.
- Se \( x \equiv 1 \), il numero è sicuramente composto.
Esempio: Nell'esempio precedente $ x = 8^2 \mod 25 = 14 $ non mi permette di affermare nulla. Quindi, devo reiterare il test su $ x = 14 $.
Il rischio dei falsi positivi
Per ogni base \( a \), la probabilità di errore del test (cioè identificare un numero composto come primo ovvero un falso positivo) è al massimo \( 1/4 \). Testando più basi, l'errore diminuisce esponenzialmente.
Quindi, è consigliabile ripetere il test $ k $ volte anche con altre basi \( a \) per ridurre la probabilità di errore.
Se il test viene ripetuto $ k $ volte con $ a $ scelto casualmente, la probabilità che un numero composto venga erroneamente identificato come primo è al massimo $ \frac{1}{4^k} $.
- Se in uno qualsiasi dei round il numero non supera i controlli, \( n \) è composto.
- Se \( n \) supera tutti i controlli per un determinato numero di basi \( a \), viene considerato "probabilmente primo".
Ad esempio, se \( n < 2^{64} \), è stato dimostrato che testare tutte le basi fino a \( \min(n-1, \lfloor 2\sqrt{\log(n)} \rfloor) \) garantisce una verifica deterministica della primalità.
Il test ha una complessità di \( O(k \cdot \log^3 n) \), dove \( k \) è il numero di basi \( a \) testate.
Esempio pratico
Verifico se \( n = 25 \) è primo.
$$ n = 25 $$
Scrivo il numero \( n-1 = 24 \) nella forma \( 2^s \cdot d \)
$$ n-1 = 24 = 2^3 \cdot 3 $$
Quindi \( s = 3 \) e \( d = 3 \).
Calcolo \( x = a^d \mod n \) scegliendo una base tra \( 2 \leq a \leq n-2 \). Ad esempio \( a = 2 \).
$$ x = a^d \mod n $$
$$ x = 2^3 \mod 25 $$
$$ x = 8 \mod 25 $$
Il risultato è $ x=8 $ perché $ 8:25 = 0 $ con resto $ r=8 $
$$ x = 8 $$
In questo caso \( x \neq 1 \) e \( x \neq n-1 = 24 \) quindi passo al test successivo.
Calcolo \( x = x^2 \mod n \) per \( s-1=3-1 = 2 \) volte.
$$ x = 8^2 \mod 25 $$
$$ x = 64 \mod 25 $$
Il risultato è $ x=14 $ perché $ 64:25 = 2 $ con resto $ r=14 $
$$ x= 14 $$
Poiché \( x \neq 24 \) continuo con la seconda iterazione.
Calcolo \( x = x^2 \mod n \) considerando l'ultimo risultato \( x=14 \).
$$ x = 14^2 \mod 25 1 $$
$$ x = 196 \mod 25 1 $$
Il risultato è $ x=21 $ perché $ 196:25 = 7 $ con resto $ r=21 $
$$ x = 21 $$
Poiché \( x \neq 24 \) ed essendo il secondo tentativo con \( s-1= 2 \) , deduco che \( 25 \) non è un numero primo, ovvero un numero è composto.
Esempio 2
Considero il numero $ n = 11 $ e verifico se è un numero primo.
Scrivo il numero $ n -1 = 10 $ nella forma $ n-1 = 2^s \cdot d $
Divido 10 per 2 e ottengo 5 che non è ulteriormente divisibile per due.
$$ n-1 = 10 = 2^1 \cdot 5 $$
Quindi \( s = 1 \) e \( d = 5 \).
Calcolo \( x = a^d \mod n \) scegliendo come base $ a = 2 $
$$ x = a^d \mod n $$
$$ x = 2^5 \mod 11 $$
$$ x = 32 \mod 11 $$
$$ x = 10 $$
Poiché $ x = n-1 = 10 $ deduco che probabilmente è un numero primo.
Per esserne più sicuro provo anche con un'altra base, ad esempio $ a = 3 $$
$$ x = a^d \mod n $$
$$ x = 3^5 \mod 11 $$
$$ x = 243 \mod 11 $$
$$ x = 1 $$
Poiché $ x = 1 $ il test di primalità è superato anche con la base $ a = 3 $ e probabilmente è un numero primo.
Nota. Ho fatto due test $ k = 2 $ scegliendo come basi $ a=2 $ e $ a=3 $ ottenendo sempre lo stesso risultato. Quindi, con la probabilità di avere ottenuto un falso positivo è molto bassa ed è pari a $ \frac{1}{4^k} = \frac{1}{4^2} = \frac{1}{16} = 0.625 $ ovvero del $ 6.25 \% $.
Esempio 3
Considero il numero $ n = 29 $
Scrivo il numero $ n -1 = 28 $ nella forma $ n-1 = 2^s \cdot d $
Divido 28 per 2 e ottengo 14, divido 14 per 2 e ottengo 7 che non è ulteriormente divisibile per due.
$$ n-1 = 28 = 2^2 \cdot 7 $$
Quindi \( s = 2 \) e \( d = 7 \).
Calcolo \( x = a^d \mod n \) scegliendo come base $ a = 2 $
$$ x = a^d \mod n $$
$$ x = 2^7 \mod 29 $$
$$ x = 128 \mod 29 $$
$$ x = 12 $$
Poiché $ x = 12 $ non supera il test di primalità, devo reiterare il test per $ s-1 = 1 $ volta.
$$ x = 12^2 \mod 29 $$
$$ x = 144 \mod 29 $$
$$ x = 28 $$
Poiché $ x = n-1 = 28 $ il test di primalità è superato con la base $ a = 2 $ e probabilmente è un numero primo.
Tuttavia, la probabilità di avere un falso positivo è ancora alta $ \frac{1}{4} = 25 \% $
Quindi, provo il test di Miller-Rabin anche con un'altra base $ a = 3 $.
$$ x = a^d \mod n $$
$$ x = 3^7 \mod 29 $$
$$ x = 2187 \mod 29 $$
$$ x = 12 $$
Poiché $ x = 12 $ non supera il test di primalità, reitero il test per $ s-1 = 1 $ volta.
$$ x = 12^2 \mod 29 $$
$$ x = 144 \mod 29 $$
$$ x = 28 $$
Poiché $ x = n-1 = 28 $ il test di primalità è superato anche con la base $ a = 3 $ e probabilmente è un numero primo.
La probabilità di avere un falso positivo è scesa a $ \frac{1}{4^2} = 6.25 \% $
Ripetendo il test anche con altre basi posso farla ridurre ulteriormente.
Note a margine
In conclusione, il test di Miller-Rabin è un metodo veloce, affidabile e semplice da implementare per determinare la primalità di numeri grandi.
E' utilizzato in molti algoritmi crittografici, come RSA, dove è fondamentale verificare la primalità di grandi numeri.
Sebbene probabilistico, con un numero sufficiente di iterazioni diventa estremamente preciso e trova ampio impiego nella pratica.
E così via.
