Test di Miller-Rabin: differenze tra le versioni

Versione delle 16:29, 7 set 2007

Versione delle 16:04, 13 set 2007

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 <math>n</math> non è maiun primo. Altrimenti n è uno pseudoprimo forte in 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: