Per renderizzare la notazione matematica presente nel post cliccate qui e aggiungete il secondo link "render mathjax" ai segnalibri, cliccatelo poi mentre siete su questa pagina e dovrebbe ricaricarla con la notazione a postohttp://www.math.ucla.edu/~robjohn/math/mathjax.html
Controllare se un numero è primo o meno è un problema che si presenta in svariate applicazioni, soprattutto di tipo crittografico e per il quale sono quindi stati sviluppati diversi algoritmi.
Solamente nel 2002 è stato dimostrato, da Agrawal, Kayal e Saxena, che controllare se un numero è primo è un problema in P tuttavia l'algoritmo di Miller-Rabin è di gran lunga il test di primalità più utilizzato nella pratica anche se è un test probabilistico per questioni di efficenza (se l'algoritmo decide che un numero non è primo allora non lo è sicuramente, mentre se decide che un numero è primo c'è una piccola probabilità che in realtà non lo sia).
Un paio di osservazioni preliminari
Per prima cosa notiamo che se $p$ è primo allora le uniche radici di $1$ modulo $p$ sono $\pm 1$, infatti $X^2-1\in\mathbb{Z}/p\mathbb{Z}[x]$ può avere al massimo $2$ radici essendo un polinomio di secondo grado a coefficenti in un campo.
Ricordiamo poi il piccolo teorema di fermat, per cui $a^{p-1}\equiv 1\pmod p$ per $p$ primo e $a$ positivo non divisibile per $p$
Il test
Sia $n>2$ primo, $n-1$ è pari ed scrivibile come $2^sd$.
Inoltre per ogni $a\in(\mathbb{Z}/p\mathbb{Z})*$ vale una delle seguenti congruenze:
$a^d\equiv 1 \pmod p$
$a^{2^rd}\equiv -1\pmod p$ per qualche $r$ con $0\le r\le s-1$
infatti per il piccolo teorema di Fermat sappiamo che $a^{p-1}\equiv 1\pmod p$ dunque $a^{2^sd}\equiv 1\pmod p$ e quindi se continuiamo ad estrarre radici quadrate dei due lati otteniamo a sinistra $a^{2^{s-1}d}$, $a^{2^{s-2}d}$ e così via mentra a destra dobbiamo continuare ad ottenere $\pm 1$ per la prima osservazione, se arriviamo a $-1$ vale la seconda equazione, mentre se il risultato è sempre $1$ ad un certo punto finiremo di poter estrarre radici quadrate (avendo esaurito le $s$ potenze di $2$) e varrà quindi la prima equazione.
Viste le osservazioni di poco fa sappiamo che se troviamo un $a$ tale che:
$a^d\not\equiv 1\pmod n$
$a^{2^rd}\not\equiv -1\pmod n$ per ogni $0\le r\le s-1$
allora $n$ non può essere primo e in questo caso chiamiamo $a$ un testimone della compositezza di $n$, altrimenti $n$ è uno pseudoprimo per la base $a$.
Per ogni $n$ non primo ci sono tanti testimoni, ma non si conosce nessun metodo efficente per generarne uno, quindi la soluzione è di rendere il test probabilistico, proviamo $k$ numeri più piccoli di $n$ e se anche un solo test fallisce allora $n$ non è primo, altrimenti lo è molto probabilmente.
In pseudocodice, dove continue è l'istruzione che interrompe l'iterazione corrente di un ciclo for per passare subito alla successiva otteniamo una cosa del genere:
Se si usa quello che in inglese vien chiamato "exponentation by squaring" e che in Italiano io conosco come "metodo del contadino russo" ma non so se ha un nome ufficiale si vede facilmente che la complessità risulta essere $O(\log^3n)$
Resta da stimare la probabilità che questo test commetta un errore, si può dimostrare (posso aggiungerlo se a qualcuno interessa, ma non volevo appesantire troppo matematicamente il post), che per ogni $n$ dispari non primo ci sono almeno $3(n-1)/4$ testimoni quindi scegliendone $k$ a caso la probabilità che $n$ non sia primo ma che ogni iterazione del test lo scambi per primo è nel caso peggiore $1/4^k$, che è praticamente trascurabile per ogni scopo pratico.
Inoltre è stato mostrato che se il numero di cui vogliamo controllare la primalità è inferiore a $2^{64}$ allora basta controllare $a=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ e $37$ per essere sicuri di non dichiarare primi numeri che non lo sono, rendendo il test di fatto deterministico ed estremamente veloce se è noto a priori un limite sui valori da testare.
Controllare se un numero è primo o meno è un problema che si presenta in svariate applicazioni, soprattutto di tipo crittografico e per il quale sono quindi stati sviluppati diversi algoritmi.
Solamente nel 2002 è stato dimostrato, da Agrawal, Kayal e Saxena, che controllare se un numero è primo è un problema in P tuttavia l'algoritmo di Miller-Rabin è di gran lunga il test di primalità più utilizzato nella pratica anche se è un test probabilistico per questioni di efficenza (se l'algoritmo decide che un numero non è primo allora non lo è sicuramente, mentre se decide che un numero è primo c'è una piccola probabilità che in realtà non lo sia).
Un paio di osservazioni preliminari
Per prima cosa notiamo che se $p$ è primo allora le uniche radici di $1$ modulo $p$ sono $\pm 1$, infatti $X^2-1\in\mathbb{Z}/p\mathbb{Z}[x]$ può avere al massimo $2$ radici essendo un polinomio di secondo grado a coefficenti in un campo.
Ricordiamo poi il piccolo teorema di fermat, per cui $a^{p-1}\equiv 1\pmod p$ per $p$ primo e $a$ positivo non divisibile per $p$
Il test
Sia $n>2$ primo, $n-1$ è pari ed scrivibile come $2^sd$.
Inoltre per ogni $a\in(\mathbb{Z}/p\mathbb{Z})*$ vale una delle seguenti congruenze:
$a^d\equiv 1 \pmod p$
$a^{2^rd}\equiv -1\pmod p$ per qualche $r$ con $0\le r\le s-1$
infatti per il piccolo teorema di Fermat sappiamo che $a^{p-1}\equiv 1\pmod p$ dunque $a^{2^sd}\equiv 1\pmod p$ e quindi se continuiamo ad estrarre radici quadrate dei due lati otteniamo a sinistra $a^{2^{s-1}d}$, $a^{2^{s-2}d}$ e così via mentra a destra dobbiamo continuare ad ottenere $\pm 1$ per la prima osservazione, se arriviamo a $-1$ vale la seconda equazione, mentre se il risultato è sempre $1$ ad un certo punto finiremo di poter estrarre radici quadrate (avendo esaurito le $s$ potenze di $2$) e varrà quindi la prima equazione.
Viste le osservazioni di poco fa sappiamo che se troviamo un $a$ tale che:
$a^d\not\equiv 1\pmod n$
$a^{2^rd}\not\equiv -1\pmod n$ per ogni $0\le r\le s-1$
allora $n$ non può essere primo e in questo caso chiamiamo $a$ un testimone della compositezza di $n$, altrimenti $n$ è uno pseudoprimo per la base $a$.
Per ogni $n$ non primo ci sono tanti testimoni, ma non si conosce nessun metodo efficente per generarne uno, quindi la soluzione è di rendere il test probabilistico, proviamo $k$ numeri più piccoli di $n$ e se anche un solo test fallisce allora $n$ non è primo, altrimenti lo è molto probabilmente.
In pseudocodice, dove continue è l'istruzione che interrompe l'iterazione corrente di un ciclo for per passare subito alla successiva otteniamo una cosa del genere:
Codice:
for i=1 to k do //k=numero di basi che testiamo
scegli a a caso in [2,n-2]
x=a^d mod p
if x==1 or x==-1 then
continue
for i=1 to r-1
x=x^2 mod n
if x==1 then
return "non primo"
if x==n-1 then
continue
return "non primo"
return "probabilmente primo"Se si usa quello che in inglese vien chiamato "exponentation by squaring" e che in Italiano io conosco come "metodo del contadino russo" ma non so se ha un nome ufficiale si vede facilmente che la complessità risulta essere $O(\log^3n)$
Resta da stimare la probabilità che questo test commetta un errore, si può dimostrare (posso aggiungerlo se a qualcuno interessa, ma non volevo appesantire troppo matematicamente il post), che per ogni $n$ dispari non primo ci sono almeno $3(n-1)/4$ testimoni quindi scegliendone $k$ a caso la probabilità che $n$ non sia primo ma che ogni iterazione del test lo scambi per primo è nel caso peggiore $1/4^k$, che è praticamente trascurabile per ogni scopo pratico.
Inoltre è stato mostrato che se il numero di cui vogliamo controllare la primalità è inferiore a $2^{64}$ allora basta controllare $a=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ e $37$ per essere sicuri di non dichiarare primi numeri che non lo sono, rendendo il test di fatto deterministico ed estremamente veloce se è noto a priori un limite sui valori da testare.
