Miller-Rabin prime test
The Miller-Rabin prime test is a probabilistic test based on the following
Let be an odd number and , odd. If and only if for every with we have
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:
Choose a random .
If , we have a non-trivial divisor of , so is not prime.
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:
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.
|Title||Miller-Rabin prime test|
|Date of creation||2013-03-22 14:54:18|
|Last modified on||2013-03-22 14:54:18|
|Last modified by||mathwizard (128)|
|Synonym||Rabin prime test|