Implementazioni di algoritmi/Test di Miller-Rabin: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
cambio avanzamento a 0% |
Nessun oggetto della modifica |
||
Riga 1:
{{implementazioni di algoritmi}}
===Test di primalità di Miller-Rabin===
[[Categoria:Implementazioni di algoritmi|Test di Primalità]]{{Avanzamento|0%|29 luglio 2008}}▼
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 e' 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>.
{{Avanzamento|0%|29 luglio 2008}}
| |||