Implementazioni di algoritmi/Test di Miller-Rabin
Test di primalità di Miller-Rabin
modificaSia 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 *t+1, con t dispari. Il test T si sintetizza nei seguenti:
- scegliamo a caso un intero b , con 1<b <n, e calcoliamo M.C.D.(b , n);
- se M.C.D.(b , n) > 1, allora n non è primo, ed abbiamo finito;
- se M.C.D.(b , n) = 1, calcoliamo b (mod n). Se b ≡ +1 (mod n) oppure b ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base b ;
- se non vale che b ≡ +1 (mod n) oppure b ≡ -1 (mod n), calcoliamo b (mod n). Se b ≡ -1 (mod n), allora n è pseudoprimo forte in base b ;
- se non vale che b ≡ -1 (mod n), passiamo a b , e a tutte le altre potenze di 2, moltiplicate per t. Se tutti i b , per r=1,..., s-1, non sono mai congrui a -1 modulo n, allora non è un primo. Altrimenti n è uno pseudoprimo forte in base b .
Per tutti gli altri test {T } , m∈ , la definizione è analoga:
- scegliamo a caso un intero b , con 1<b <n, e calcoliamo M.C.D.(b , n);
- se M.C.D.(b , n) > 1, allora n non è primo, ed abbiamo finito;
- se M.C.D.(b , n) = 1, calcoliamo b (mod n), e procediamo come nel primo test. In questo modo troviamo che p non è primo, oppure che n è pseudoprimo forte in base b .