Implementazioni di algoritmi/Test di Miller-Rabin

Test di primalità di Miller-Rabin

Sia n un numero intero positivo dispari e non primo. I numeri positivi b<n tali che M.C.D.(b,n)=1, e tali che n sia uno pseudoprimo di Eulero forte in base b sono non più di un quarto di tutti i numeri positivi b<n tali che M.C.D.(b,n)=1.

Questo è il test di primalita' che stavamo presentando:

Se fisso un intero dispari n>1, lo posso scrivere come n=2$s^{}$*t+1, con t dispari. Il test T${}_1$ si sintetizza nei seguenti:

1. scegliamo a caso un intero b${}_1$, con 1<b${}_1$<n, e calcoliamo M.C.D.(b${}_1$, n);
2. se M.C.D.(b${}_1$, n) > 1, allora n non è primo, ed abbiamo finito;
3. se M.C.D.(b${}_1$, n) = 1, calcoliamo b$\underset{t}{\overset{}{1}}$ (mod n). Se b$\underset{t}{\overset{}{1}}$ ≡ +1 (mod n) oppure b$\underset{t}{\overset{}{1}}$ ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base b${}_1$;
4. se non vale che b$\underset{t}{\overset{}{1}}$ ≡ +1 (mod n) oppure b$\underset{t}{\overset{}{1}}$ ≡ -1 (mod n), calcoliamo b$\underset{2t}{\overset{}{1}}$ (mod n). Se b$\underset{2t}{\overset{}{1}}$ ≡ -1 (mod n), allora n è pseudoprimo forte in base b${}_1$;
5. se non vale che b$\underset{2t}{\overset{}{1}}$ ≡ -1 (mod n), passiamo a b$\underset{4t}{\overset{}{1}}$, e a tutte le altre potenze di 2, moltiplicate per t. Se tutti i b$\underset{2^r*t}{\overset{}{1}}$, per r=1,..., s-1, non sono mai congrui a -1 modulo n, allora $n$ non è un primo. Altrimenti n è uno pseudoprimo forte in base b${}_1$.

Per tutti gli altri test {T${}_m$}${}_m$, m∈$\mathbb{N}$, la definizione è analoga:

1. scegliamo a caso un intero b${}_m$, con 1<b${}_m$<n, e calcoliamo M.C.D.(b${}_m$, n);
2. se M.C.D.(b${}_m$, n) > 1, allora n non è primo, ed abbiamo finito;
3. se M.C.D.(b${}_m$, n) = 1, calcoliamo b$\underset{t}{\overset{}{m}}$ (mod n), e procediamo come nel primo test. In questo modo troviamo che p non è primo, oppure che n è pseudoprimo forte in base b${}_m$.