SolovayStrassen test
It is known that an odd number^{} $n$ is prime if and only if for every $$ such that $(a,n)=1$ we have
$$\left(\frac{a}{n}\right)\equiv {a}^{\frac{n1}{2}}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$$  (1) 
where $\left(\frac{a}{n}\right)$ is the Jacobi symbol^{}. (The only if part is obvious; the if part follows from Theorem 1.) From this we can derive the following algorithm^{}.

1.
Choose a random number $a$ between $1$ and $n1$.

2.
Check if $(a,n)=1$ (for example using the Euclidean algorithm^{}). If it is not, then $n$ is not prime and $(a,n)$ is a divisor^{} of $n$.
 3.
By repeating this algorithm we can increase the chance that the result is correct. In order to estimate the probability of error, we make use of Theorem 1, which says that every independent iteration of the algorithm has a chance of at most $50\%$ of being wrong. Hence, after $t$ iterations there is at most a ${2}^{t}$ chance of getting a wrong result.
Theorem 1.
Proof.
It suffices to exhibit one element $a\in {\mathbb{Z}}_{n}^{*}$ which does not satisfy Equation (1). Indeed, if there exists one such element, then the set of all elements which do satisfy Equation (1) forms a proper subgroup^{} of ${\mathbb{Z}}_{n}^{*}$, from which we conclude that the elements satisfying Equation (1) number no more than half of the elements of ${\mathbb{Z}}_{n}^{*}$.
We consider separately the cases where $n$ is squarefree^{} and not squarefree. If $n$ is squarefree, let $p$ be a prime dividing $n$ and let $b$ be a quadratic nonresidue mod $n$. Using the Chinese Remainder Theorem^{}, choose an integer $a\in {\mathbb{Z}}_{n}^{*}$ such that:
$a$  $\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modp),$  
$a$  $\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod{\displaystyle \frac{n}{p}}).$ 
The Jacobi symbol $\left(\frac{a}{n}\right)$ is given by
$$\left(\frac{a}{n}\right)=\left(\frac{a}{p}\right)\left(\frac{a}{n/p}\right)=\left(\frac{b}{p}\right)\left(\frac{1}{n/p}\right)=(1)\cdot 1=1.$$ 
We will assume that ${a}^{\frac{n1}{2}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ and derive a contradiction^{}. The equation ${a}^{\frac{n1}{2}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ implies that ${a}^{\frac{n1}{2}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod\frac{n}{p})$. However, since $a\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod\frac{n}{p})$, we must have ${a}^{\frac{n1}{2}}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod\frac{n}{p})$, so that $1\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod\frac{n}{p})$, which is a contradiction.
Now suppose that $n$ is not squarefree. Let $p$ be a prime such that ${p}^{2}\mid n$, and set $a=1+\frac{n}{p}$. By the binomial theorem^{}, we have
$${a}^{p}={\left(1+\frac{n}{p}\right)}^{p}=1+\left(\genfrac{}{}{0pt}{}{p}{1}\right)\left(n/p\right)+\left(\genfrac{}{}{0pt}{}{p}{2}\right){\left(n/p\right)}^{2}+\mathrm{\cdots}+\left(\genfrac{}{}{0pt}{}{p}{p}\right){\left(n/p\right)}^{p}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn),$$ 
so the multiplicative order^{} of $amodn$ is equal to $p$, and hence in particular ${a}^{n1}\ne 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$, since $p\nmid n1$. On the other hand,
$$\left(\frac{a}{n}\right)=\left(\frac{1+\frac{n}{p}}{n}\right)=\left(\frac{1+\frac{n}{p}}{p}\right)\left(\frac{1+\frac{n}{p}}{n/p}\right)=\left(\frac{1}{p}\right)\left(\frac{1}{n/p}\right)=1,$$ 
so $a$ does not satisfy Equation (1). ∎
Title  SolovayStrassen test 

Canonical name  SolovayStrassenTest 
Date of creation  20130322 14:27:33 
Last modified on  20130322 14:27:33 
Owner  mathwizard (128) 
Last modified by  mathwizard (128) 
Numerical id  7 
Author  mathwizard (128) 
Entry type  Algorithm 
Classification  msc 11Y11 
Related topic  MillerRabinPrimeTest 