Test di Miller-Rabin: differenze tra le versioni

Versione delle 16:19, 19 set 2014

Versione delle 12:50, 30 giu 2015

Riga 8:

Questo è il test di primalità che stavamo presentando:

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

# scegliamo a caso un intero b<math>_1</math>, con 1<b<math>_1</math><n, e calcoliamo M.C.D.(b<math>_1</math>, n);

# se M.C.D.(b<math>_1</math>, n) > 1, allora n non è primo, ed abbiamo finito;