Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test.

Specifically: I understand that for some reason, having non-trivial square roots of 1 mod p means that p is definitely composite; and I gather that you can find these non-trivial square roots by squaring x, but I don't really understand what these reasons are. Specific examples of non-trivial roots of a composite number would be helpful.


  • $\begingroup$ What don't you understand about the explanation at the Wikipedia article, which also includes examples? $\endgroup$ – Qiaochu Yuan Sep 14 '10 at 5:09
  • 7
    $\begingroup$ I still think it is disingenuous to term it a "primality" test; better that it be called a "compositeness test". If a number fails it, it is definitely composite, but a number passing this does not necessarily imply that the number is prime. $\endgroup$ – J. M. isn't a mathematician Sep 14 '10 at 5:50
  • $\begingroup$ @Qiaochu - the examples there just provide the steps, which I can easily reproduce. However, the examples don't walk you through it step by step. For instance, they talk about non-trivial roots (which as I understand it, is the fundamental concept behind the MR Test) but they never give an example of a non-trivial root. $\endgroup$ – Smashery Sep 14 '10 at 6:04
  • $\begingroup$ You might also be interested in reading jjj.de/fxt/fxtpage.html#fxtbook ; he gives a nice little description of Miller-Rabin and other related tests. $\endgroup$ – J. M. isn't a mathematician Sep 14 '10 at 6:41

Suppose $p$ was prime, and $y$ was a non-trivial square root of $1$ mod $p$.

Then we must have that $y^2 = 1 \mod p$ and so $(y-1)(y+1) = 0 \mod p$. This implies that either $y = 1 \mod p$ or $y = -1 \mod p$, which implies that $y$ is a trivial square root.

Thus, if there is a non-trivial square root of $1$ mod $p$, then $p$ has to be composite.

For an example of a non trivial square root of a composite, consider $p = 15$. We have that $4^2 = 16 = 1 \mod 15$. Thus $15$ is composite.

Note that the witness in the primality test is not necessarily a non-trivial square root of $1$ mod $p$.

The fact about non-trivial square roots can be used to prove that if $p$ is prime, then for any $a$ relatively prime to $p$, some power of $a$ from a given set of powers (the powers are based on the even factors of $p-1$) must be $-1$ or a specific odd power of $a$ (again based on factor of $p-1$) must be $1$.

If for some $a$ none of the above set of powers is $-1$ and the specific odd power is not $1$, then it must be the fact that $p$ is composite.

It can also be shown that for composite $p$, the chances of finding such $a$ is atleast $3/4$. This $a$ is the witness in the primality test and is not necessarily a non-trivial square root of $1$ mod $p$.

The squaring that is done is to get the powers described above which are based on the factors of $p-1$.

The wiki page has really got a lot of good information (including the exact powers of $a$ that need to be taken): Miller Rabin Primality Test

  • $\begingroup$ +1 - Thanks; very clear. Two things I still don't understand: why do we use even factors of p-1 for our testing; and once we get to -1 or 1, why are we so sure it's composite/probable prime? $\endgroup$ – Smashery Sep 14 '10 at 6:25
  • 2
    $\begingroup$ @Smash: The reason we take factors of p-1 is that by Fermat's little theorem a^(p-1) = 1 mod p if p is prime. So if p-1 = 2^{r}.s. We also have that (a^{2^{i}}.s)^{2} = a^{2^{i+1}s), so we get square roots of 1 among those powers. The wiki page has a good write up of that. $\endgroup$ – Aryabhata Sep 14 '10 at 13:57

Below is little-known general yet simple answer to your question about nontrivial sqrts $\rm (mod\ m)\:$.

Theorem $ $ We can quickly split $\rm m>1\,$ into two nontrivial factors given a nonzero polynomial with more roots mod $\rm\, m\,$ than its degree.

Proof $ $ By hypothesis $\rm\, \color{#0a0}{0\not\equiv} f(x)\,$ has degree $\rm\,n\,$ and at least $\rm\,n\!+\!1 \,$ distinct roots $\rm\,r,\,r_1,\,\ldots,\,r_n.\,$ Inductively applying the the Factor Theorem as here yields $\rm\,f(x) \equiv c(x\!-\!r_1)\cdots(x\!-\!r_{n}),\ c\color{#0a0}{\not\equiv 0}.\,$ Since also $\rm\,f(r)\equiv 0\,$ we infer $\rm\,m\mid c(r\!-\!r_1)\cdots (r\!-\!r_n).\,$ If $\rm\,m\,$ were coprime to all those factors it would be coprime to their product by Euclid's Lemma. Since it is not, we deduce that $\rm\,m\,$ is not coprime to some factor $\rm\,k.\,$ Since $\,\rm m\,$ divides none of the factors (by the roots are distinct $\rm\!\bmod m\,$ and $\,c\color{#0a0}{\not\equiv 0}),\,$ we infer $\,\rm\gcd(m,k)\neq m,\,$ thus the gcd is a nontrivial factor of $\,\rm m,\,$ being $\rm\neq 1,m.\ $

Example $\rm\;(deg\ f = 1)\;\,$ Suppose, mod $\rm\,m,\,$ that $\rm\; 0 \,\not\equiv\, f \,=\, a\,x\;$ has a "nontrivial" root $\rm\, b\not\equiv 0.\,$ Then $\rm\; m\mid ab,\,\ m\nmid a,b \;\Rightarrow\,$ $\,\rm gcd(m,b)\,$ is a factor of $\rm\, m\,$ that is nontrivial $(\neq 1,\,m),\,$ i.e. $ $ when $\rm\, m\,$ fails the Prime Divisor Property (Euclid's Lemma) it is constructively composite.

Example $\rm\;(deg\ f = 2)\;\,$ Suppose, modulo $\rm\,m\,$, $\rm\; x^2 \equiv 1\,$ has a "nontrivial" square root $\rm\, b\not\equiv \pm1.\,$ Then $\;\rm gcd(m,b\pm 1)\;$ yields a nontrivial factor of $\rm\, m\,$ when $\rm\, m\,$ is odd. This idea lies at the heart of many integer factorization algorithms. In detail, by unique prime factorization we have $\rm\, m\mid (b\!-\!1)(b\!+\!1)\,\Rightarrow\, m = jk,\,\ j\mid b\!-\!1,\, k\mid b\!+\!1,\,$ so $\rm\,m\nmid b\pm 1\,\Rightarrow\,j,k\mid m\,$ nontrivially.

The above proof easily extends to yield a proof of the following

Theorem $ $ A ring $\rm\, R$ is an (integral) domain, i.e. $\rm\,rs = 0\,\Rightarrow\, r=0\,$ or $\rm\,s =0,\,$ for all $\rm\,r,s\in R$ $\iff$ every nonzero polynomial $\,\rm f(x)\in R[x]\,$ has at most $\rm\, deg\ f(x)\,$ roots in $\rm R$

Proof $\ $ $(\Rightarrow)\;$ Employ induction on the polynomial degree, as in the proof of the above Theorem. $(\Leftarrow)\ \ $ If $\rm\; r \ne 0\;$ then the polynomial $\rm\, rx\,$ has only the root $\rm\; x = 0,\,$ hence $\rm\ rs = 0 \ \Rightarrow\ s = 0$.

  • 1
    $\begingroup$ I'm sorry - I don't understand much of that. $\endgroup$ – Smashery Sep 14 '10 at 6:35
  • 2
    $\begingroup$ @Smashery: I completely revised the answer to be both simpler and much more general. Please let me know if anything is still unclear. See esp. the second example. $\endgroup$ – Bill Dubuque Sep 15 '10 at 1:35
  • 2
    $\begingroup$ I'd give this a second vote if I could. $\endgroup$ – Charles Dec 11 '10 at 1:38
  • $\begingroup$ when you typed two nontrial factors, did you mean two nontrivial factors? $\endgroup$ – J. W. Tanner Mar 16 '20 at 0:03
  • $\begingroup$ @J.W.Tanner Yes, of course, thanks. $\endgroup$ – Bill Dubuque Mar 16 '20 at 0:04

If $p$ is prime then $\mathbb{Z}_p$ (integers modulo $p$) is a field. It is a basic result in algebra that in a field, a polynomial of degree $n$ has at most $n$ roots, and so the polynomial $x^2-1$ has exactly two roots: $1$ and $-1$ (which exist in every field).

If $n$ is composite, then $\mathbb{Z}_n$ is never a field because not all elements have an inverse; it it well known that $a\in \mathbb{Z}_n$ has an inverse if and only if $a$ is relatively prime to $n$. Let's look at the case $n$ is the product of two primes, $n=pq$. In this case we can do arithmetic in $\mathbb{Z}_n$ by doing arithmetic in $\mathbb{Z}_p$ and $\mathbb{Z}_q$ and combining the results using the Chinese remainder theorem (which basically states that $\mathbb{Z}_n\cong\mathbb{Z}_p\times\mathbb{Z}_q$. Since $\mathbb{Z}_p$ and $\mathbb{Z}_q$ are both fields, $1$ has two roots in each of them. For every combination of a root from $\mathbb{Z}_p$ and a root from $\mathbb{Z}_q$ we'll get a root of 1 in $\mathbb{Z}_n$, meaning we'll get 4 roots of 1.

The major challenge of the Miller-Rabin test is to show that there is a "large" chance to stumble upon a non-trivial root while squaring random elements of $\mathbb{Z}_n$, and the proof, although not difficult, is not immediate either.

  • 1
    $\begingroup$ Caution the result fails for p = 2 since 1 = -1 yields only 1 root. $\endgroup$ – Bill Dubuque Sep 14 '10 at 6:03
  • $\begingroup$ To be fair, a lot of things in number theory about primes fail for 2. Hence the frequent "Let $p$ be an odd prime..." $\endgroup$ – J. M. isn't a mathematician Sep 14 '10 at 6:14
  • $\begingroup$ So where does the squaring come in? The step of x = x^2 still confuses me. $\endgroup$ – Smashery Sep 14 '10 at 6:26
  • $\begingroup$ Smashery: It's modular exponentiation. Square x and take the appropriate remainder. $\endgroup$ – J. M. isn't a mathematician Sep 14 '10 at 6:39
  • 2
    $\begingroup$ Miller-Rabin is basically a smart version of the Fermat test. In the Fermat test, you choose some a at random and compute a^{n-1} and compare it to 1. Computing the (n-1)th power is slow if it's done directly, so the trick is to cut time by repeated squaring. The extra idea Miller-Rabin adds is to verify that during this squaring process we don't gain nontrivial roots of 1. $\endgroup$ – Gadi A Sep 15 '10 at 14:20

A test based on Fermat’s Theorem ($a^{n-1} \equiv 1 \pmod n$ if n is prime)

-For a candidate odd integer n (3), consider $(n-1)$ s.t. $n-1=2^kq$ with $k>0$, $q$ odd

That is, we divide (n-1) by 2 until the result is an odd number, for a total of $k$ divisions.

-Next we choose an integer $a$ ($1 < a < n - 1 $).

Then involve computation of the residues modulo n of the following sequence of powers

-$a^q, a^{2q}, ..., a^{2^{k-1}q}$, $a^{2^kq}$

-If $n$ is prime, $a^{(2k-1)q} \equiv a^{n-1} \equiv 1 \pmod n$.

-There may or may not be an earlier element of the sequence that has a residue 1

-If n is prime, there is a smallest value of j ($0<j<k$) such that $a^{2jq}\equiv 1 \pmod n$.

-There are two cases to consider

-Case 1 ($j=0$) : We have $a^{q–1} \equiv 0 \pmod n$

-Case 2 ($1<j<k$) : $(a^{2^jq}-1) \equiv (a^{2^{j-1}q}-1)(a^{2^{j+1}q}+1) \equiv 0 \pmod n$.

Because j is the smallest integer s.t. n divides $(a^{2^jq}-1)$, n divides $(a2^{(j+1)q}+1)$

A test based on Fermat’s Theorem ($a^{n-1} \equiv 1 \pmod n$ if $n$ is prime)

-Algorithm is: TEST (n) is:

  1. Find integers $k$, $q$, $k > 0$, $q$ odd, so that $(n–1)=2^kq$

  2. Select a random integer a, 1

  3. if $a^q \equiv 1 \pmod n$ then return (“maybe prime");

  4. for j = 0 to k –1 do

  5. if($a^{2^jq} \mod n = n-1$) then return(" maybe prime ")

  6. return ("composite")

  • $\begingroup$ I tried to edit/TeXify your answer as well as I was able to. You might want to have a look whether my edits follow your original intentions. It might also help you to get basics of the TeX syntax in the way it is used at this site. $\endgroup$ – Martin Sleziak May 27 '11 at 12:50
  • $\begingroup$ Brilliant proof. There are some mistakes of Latex of the exponents. $\endgroup$ – alinsoar Oct 27 '12 at 23:31

It took me ages to find out but I realized the trick is just a bit of factorization.

Fermat theorem says that if $p$ is prime, then $a^{p-1} \equiv 1\ (\text{mod}\ p)$.

Or in other words $a^{p-1} - 1$ is divided by $p$ if it's prime for all $a$.

Now the idea behind the Miller-Rabin test is factorizing this expression. You express $p - 1 = 2^k d$, where $d$ is odd.

Now you can factorize $a^{p-1} - 1 = a^{2^k d} - 1$:

$a^{2^k d} - 1 = (a^{2^{k-1} d} - 1)(a^{2^{k-1} d} + 1)$

The $a^{2^{k-1} d} - 1$ term can be factorized further:

$a^{2^{k-1} d} - 1 = (a^{2^{k-2} d} - 1)(a^{2^{k-2} d} + 1)$

And so on. At the end you have:

$a^{2^k d} - 1 = (a^d - 1)(a^d + 1)(a^{2d} + 1)(a^{4d} + 1)...(a^{2^{k-1}d} + 1)$

So far we just factored the expression and if $p$ is prime, it will divide it.

If $p$ is really prime, it must divide at least one of the factors in the factorization above, because it must appear as a prime factor in one of these factors (Euclid's lemma).

So the test $a^{d} \equiv 1\ (\text{mod}\ p)$ corresponds to the first factor. The tests $a^{2^{i}d} \equiv -1\ (\text{mod}\ p)$ corresponds to the rest of the factors.

If the whole thing is divisible by $p$, but none of the factors are divisible by $p$, then that indicates the prime factors of $p$ is distributed between more than one factors and none of them has all of it, and this proves $p$ is composite. Otherwise it may be prime.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.