# Implementazioni di algoritmi/Test di Miller-Rabin

Implementazioni di algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaImplementazioni di algoritmi/Copertina
* Algoritmo di EuclideImplementazioni di algoritmi/Algoritmo di Euclide
* Elevazione a potenzaImplementazioni di algoritmi/Elevazione a potenza
* Prodotto scalareImplementazioni di algoritmi/Prodotto scalare
* Calcolo della PasquaImplementazioni di algoritmi/Calcolo della Pasqua
* Metodo Monte CarloImplementazioni di algoritmi/Metodo Monte Carlo
* Ricerca
** Ricerca dicotomicaImplementazioni di algoritmi/Ricerca dicotomica
* Numeri primi
** Crivello di EratosteneImplementazioni di algoritmi/Crivello di Eratostene
** Test di primalità
*** Test deterministicoImplementazioni di algoritmi/Test deterministico
*** Test di Miller-RabinImplementazioni di algoritmi/Test di Miller-Rabin
* PRNG
** Mersenne TwisterImplementazioni di algoritmi/Mersenne Twister
** Test Chi QuadratoImplementazioni di algoritmi/Test Chi Quadrato
* Crittografia
** RSAImplementazioni di algoritmi/RSA
** TEAImplementazioni di algoritmi/TEA
* π(Metodi per definire il pi greco)
** Pi grecoImplementazioni di algoritmi/Pi greco
* Algoritmi di ordinamento
** Bubble sortImplementazioni di algoritmi/Bubble sort
** Bucket sortImplementazioni di algoritmi/Bucket sort
** Counting sortImplementazioni di algoritmi/Counting sort
** Gnome sortImplementazioni di algoritmi/Gnome sort
** Insertion sortImplementazioni di algoritmi/Insertion sort
** Merge sortImplementazioni di algoritmi/Merge sort
** QuicksortImplementazioni di algoritmi/Quicksort
** Radix sortImplementazioni di algoritmi/Radix sort
** Selection sortImplementazioni di algoritmi/Selection sort
** Shaker sortImplementazioni di algoritmi/Shaker sort
** Shell sortImplementazioni di algoritmi/Shell sort
Modifica il sommario

### 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$^{s}$*t+1, con t dispari. Il test T$_{1}$ si sintetizza nei seguenti:
* scegliamo a caso un intero b$_{1}$, con 1<b$_{1}$<n, e calcoliamo M.C.D.(b$_{1}$, n);
* se M.C.D.(b$_{1}$, n) > 1, allora n non è primo, ed abbiamo finito;
* se M.C.D.(b$_{1}$, n) = 1, calcoliamo b$_{1}^{t}$ (mod n). Se b$_{1}^{t}$ ≡ +1 (mod n) oppure b$_{1}^{t}$ ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base b$_{1}$;
* se non vale che b$_{1}^{t}$ ≡ +1 (mod n) oppure b$_{1}^{t}$ ≡ -1 (mod n), calcoliamo b$_{1}^{2t}$ (mod n). Se b$_{1}^{2t}$ ≡ -1 (mod n), allora n è pseudoprimo forte in base b$_{1}$;
* se non vale che b$_{1}^{2t}$ ≡ -1 (mod n), passiamo a b$_{1}^{4t}$, e a tutte le altre potenze di 2, moltiplicate per t. Se tutti i b$_{1}^{2^{r}*t}$, per r=1,..., s-1, non sono mai congrui a -1 modulo n, allora $n$ non è un primo. Altrimenti n è uno pseudoprimo forte in base b$_{1}$.
Per tutti gli altri test {T$_{m}$}$_{m}$, m∈$\mathbb {N}$, la definizione è analoga:
* scegliamo a caso un intero b$_{m}$, con 1<b$_{m}$<n, e calcoliamo M.C.D.(b$_{m}$, n);
* se M.C.D.(b$_{m}$, n) > 1, allora n non è primo, ed abbiamo finito;
* se M.C.D.(b$_{m}$, n) = 1, calcoliamo b$_{m}^{t}$ (mod n), e procediamo come nel primo test. In questo modo troviamo che p non è primo, oppure che n è pseudoprimo forte in base b$_{m}$.