Miller-Rabin prime test
The Miller-Rabin prime test is a probabilistic test based on the following
Theorem 1.
Let be an odd number and , odd. If and only if for every with we have
(1a) | |||
(1b) |
for some , then is prime. If is not prime, then let be the set of all satisfying the above conditions. We have
where is Euler’s Phi-function.
A composite number satisfying conditions (1) for some is called a strong in the basis . Note that this theorem states that there are no such things as Carmichael numbers for strong pseudoprimes (i.e. composite numbers that are strong pseudoprimes for all values of ). From this theorem we can construct the following algorithm:
-
1.
Choose a random .
-
2.
If , we have a non-trivial divisor of , so is not prime.
-
3.
If , check if the conditions (1) are satisfied. If not, is not prime, otherwise the probability that is not prime is less than .
In general the probability, that the test falsely reports as a prime is far less than . Of course the algorithm can be applied several times in order to reduce the probability, that is not a prime but reported as one.
When comparing this test with the related Solovay-Strassen test one sees that this test is superior is several ways:
-
•
There is no need to calculate the Jacobi symbol.
-
•
The amount of false witnesses, i.e. numbers that report as a prime when it is not, is at most instead of .
-
•
One can even show that which passes Miller-Rabin for some also passes Solovay-Strassen for that , so Miller-Rabin is always better.
Note that when the test returns that is composite, then this is indeed the case, so it is really a compositeness test rather than a test for primality.
Title | Miller-Rabin prime test |
---|---|
Canonical name | MillerRabinPrimeTest |
Date of creation | 2013-03-22 14:54:18 |
Last modified on | 2013-03-22 14:54:18 |
Owner | mathwizard (128) |
Last modified by | mathwizard (128) |
Numerical id | 9 |
Author | mathwizard (128) |
Entry type | Algorithm |
Classification | msc 11Y11 |
Synonym | Rabin prime test |
Related topic | SolovayStrassenTest |
Related topic | FermatCompositenessTest |
Defines | strong pseudoprime |