Test di Miller-Rabin: differenze tra le versioni

Versione delle 12:22, 11 mar 2013

Versione delle 13:52, 1 nov 2013

Riga 2:

Il '''test di primalità di Miller-Rabin''' è un [[test di primalità]], ossia un [[algoritmo]] per determinare se un [[numero intero]] è [[numero primo|primo]]. La sua versione originale, dovuta a [[Gary Miller]], è deterministica, ma dipende dall'[[ipotesi di Riemann generalizzata]], un'importante [[congettura]] matematica tuttora aperta. L'algoritmo è stato successivamente modificato da [[Michael Rabin]] che ne ha ottenuto una versione [[algoritmo probabilistico|probabilistica]] simile ai [[test di Fermat]] e di [[test di Solovay-Strassen]].

==Definizione==

==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 forte|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.