Implementazioni di algoritmi/Test di Miller-Rabin: differenze tra le versioni

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.

 

 

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