MillerRabin prime test
The MillerRabin prime test is a probabilistic test based on the following
Theorem 1.
Let $N\mathrm{\ge}\mathrm{3}$ be an odd number^{} and $N\mathrm{}\mathrm{1}\mathrm{=}{\mathrm{2}}^{t}\mathit{}n$, $n$ odd. If and only if for every $a\mathrm{\in}\mathrm{Z}$ with $\mathrm{gcd}\mathit{}\mathrm{(}a\mathrm{,}N\mathrm{)}\mathrm{=}\mathrm{1}$ we have
$${a}^{n}\equiv 1\mathit{\hspace{1em}}\mathit{\text{mod}}N\mathit{\hspace{1em}\hspace{1em}}\text{\mathit{o}\mathit{r}}$$  (1a)  
$${a}^{{2}^{s}n}\equiv 1\mathit{\hspace{1em}}\mathit{\text{mod}}N$$  (1b) 
for some $s\mathrm{\in}\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{\dots}\mathrm{,}t\mathrm{}\mathrm{1}\mathrm{\}}$, 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{\mathit{C}\mathit{a}\mathit{r}\mathit{d}}(A)\le \frac{1}{4}\phi (N),$$ 
where $\phi $ is Euler’s Phifunction.
A composite number^{} $N$ satisfying conditions (1) for some $a\in \mathbb{Z}$ is called a strong 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^{}:

1.
Choose a random $2\le a\le N1$.

2.
If $\mathrm{gcd}(a,N)\ne 1$, we have a nontrivial divisor^{} of $N$, so $N$ is not prime.

3.
If $\mathrm{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 SolovayStrassen 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 MillerRabin for some $a$ also passes SolovayStrassen for that $a$, so MillerRabin 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.
Title  MillerRabin prime test 

Canonical name  MillerRabinPrimeTest 
Date of creation  20130322 14:54:18 
Last modified on  20130322 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 