# Split $n$ into nontrivial factors via a nontrivial square-root of $1\!\pmod{\!n}$

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.

Cheers!

• What don't you understand about the explanation at the Wikipedia article, which also includes examples? Sep 14, 2010 at 5:09
• 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. Sep 14, 2010 at 5:50
• @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. Sep 14, 2010 at 6:04
• 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. Sep 14, 2010 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

• +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? Sep 14, 2010 at 6:25
• @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. Sep 14, 2010 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$$.

• I'm sorry - I don't understand much of that. Sep 14, 2010 at 6:35
• @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. Sep 15, 2010 at 1:35
• I'd give this a second vote if I could. Dec 11, 2010 at 1:38
• when you typed two nontrial factors, did you mean two nontrivial factors? Mar 16, 2020 at 0:03
• @J.W.Tanner Yes, of course, thanks. Mar 16, 2020 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.

• Caution the result fails for p = 2 since 1 = -1 yields only 1 root. Sep 14, 2010 at 6:03
• To be fair, a lot of things in number theory about primes fail for 2. Hence the frequent "Let $p$ be an odd prime..." Sep 14, 2010 at 6:14
• So where does the squaring come in? The step of x = x^2 still confuses me. Sep 14, 2010 at 6:26
• Smashery: It's modular exponentiation. Square x and take the appropriate remainder. Sep 14, 2010 at 6:39
• 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. Sep 15, 2010 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")

• 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. May 27, 2011 at 12:50
• Brilliant proof. There are some mistakes of Latex of the exponents. Oct 27, 2012 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.