Test di Miller-Rabin: differenze tra le versioni

Versione delle 12:58, 28 giu 2007

Versione delle 21:34, 1 lug 2007

Riga 5:

===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 ununo pseudoprimo 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.

In base a questa proposizione possiamo mostrare il test che stavamo presentando.

Riga 14:

# se M.C.D.(b<math>_1</math>, n) = 1, calcoliamo b<math>_1^{t}</math> (mod n). Se b<math>_1^{t}</math> ≡ +1 (mod n) oppure b<math>_1^{t}</math> ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base b<math>_1</math>;

# se non vale che b<math>_1^{t}</math> ≡ +1 (mod n) oppure b<math>_1^{t}</math> ≡ -1 (mod n), calcoliamo b<math>_1^{2t}</math> (mod n). Se b<math>_1^{2t}</math> ≡ -1 (mod n), allora n è pseudoprimo forte in base b<math>_1</math>;

# se non vale che b<math>_1^{2t}</math> ≡ -1 (mod n), passiamo a b<math>_1^{4t}</math>, e a tutte le altre potenze di 2, moltiplicate per t. Se tutti i b<math>_1^{2^{r}*t}</math>, per r=1,..., s-1, non sono mai congrui a "-1" modulo n, allora n non è mai primo. Altrimenti n è uno pseudoprimo forte i base b<math>_1</math>.

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