|
|
|
|
Miller-Rabin prime test
|
(Algorithm)
|
|
|
The Miller-Rabin prime test is a probabilistic test based on the following
Theorem 1 Let $N\geq 3$ be an odd number and $N-1=2^tn$ , $n$ odd. If and only if for every $a\in\mathbb{Z}$ with $\gcd(a,N)=1$ we have
for some $s\in\{0,\dots,t-1\}$ , then $N$ is prime. If $N$ is not prime, then let $A$ be the set of all $a$ satisfying the above conditions. We have $$\text{Card}(A)\leq\frac{1}{4}\varphi(N),$$ where $\varphi$ is Euler's Phi-function.
A composite number $N$ satisfying conditions (1) for some $a\in\mathbb{Z}$ is called a strong pseudoprime in the basis $a$ . 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 $a$ ). From this theorem we can construct the following algorithm:
- Choose a random $2\leq a\leq N-1$ .
- If $\gcd(a,N)\neq 1$ , we have a non-trivial divisor of $N$ , so $N$ is not prime.
- If $\gcd(a,N)=1$ , check if the conditions (1) are satisfied. If not, $N$ is not prime, otherwise the probability that $N$ is not prime is less than $\frac{1}{4}$ .
In general the probability, that the test falsely reports $N$ as a prime is far less than $\frac{1}{4}$ . Of course the algorithm can be applied several times in order to reduce the probability, that $N$ 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 $a$ that report $N$ as a prime when it is not, is at most $\frac{N}{4}$ instead of $\frac{N}{2}$ .
- One can even show that $N$ which passes Miller-Rabin for some $a$ also passes Solovay-Strassen for that $a$ , so Miller-Rabin is always better.
Note that when the test returns that $N$ is composite, then this is indeed the case, so it is really a compositeness test rather than a test for primality.
|
"Miller-Rabin prime test" is owned by mathwizard.
|
|
(view preamble | get metadata)
Cross-references: primality, even, numbers, witnesses, Jacobi symbol, calculate, Solovay-Strassen test, order, divisor, algorithm, Carmichael numbers, theorem, basis, composite number, Euler's, prime, odd, odd number
This is version 6 of Miller-Rabin prime test, born on 2004-12-21, modified 2005-02-23.
Object id is 6589, canonical name is MillerRabinPrimeTest.
Accessed 12262 times total.
Classification:
| AMS MSC: | 11Y11 (Number theory :: Computational number theory :: Primality) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
