Visualizza wikitesto di Implementazioni di algoritmi/Test di Miller-Rabin

{{implementazioni di algoritmi}}
===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 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<math>^{s}</math>*t+1, 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;
# 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 è un 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:

# scegliamo a caso un intero b<math>_m</math>, con 1<b<math>_m</math><n, e calcoliamo M.C.D.(b<math>_m</math>, n);
# se M.C.D.(b<math>_m</math>, n) > 1, allora n non è primo, ed abbiamo finito;
# se M.C.D.(b<math>_m</math>, n) = 1, calcoliamo b<math>_m^{t}</math> (mod n), e procediamo come nel primo test. In questo modo troviamo che p non è primo, oppure che n è pseudoprimo forte in base b<math>_m</math>.

[[Categoria:Implementazioni di algoritmi|Test di Primalità]]
{{Avanzamento|0%|29 luglio 2008}}