# 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? – Qiaochu Yuan Sep 14 '10 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. – J. M. isn't a mathematician Sep 14 '10 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. – Smashery Sep 14 '10 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. – 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

• +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? – Smashery Sep 14 '10 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. – 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$$.

• I'm sorry - I don't understand much of that. – Smashery Sep 14 '10 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. – Gone Sep 15 '10 at 1:35
• I'd give this a second vote if I could. – Charles Dec 11 '10 at 1:38
• when you typed two nontrial factors, did you mean two nontrivial factors? – J. W. Tanner Mar 16 at 0:03
• @J.W.Tanner Yes, of course, thanks. – Gone Mar 16 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. – Gone Sep 14 '10 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..." – J. M. isn't a mathematician Sep 14 '10 at 6:14
• So where does the squaring come in? The step of x = x^2 still confuses me. – Smashery Sep 14 '10 at 6:26
• Smashery: It's modular exponentiation. Square x and take the appropriate remainder. – J. M. isn't a mathematician Sep 14 '10 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. – 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")

• 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. – Martin Sleziak May 27 '11 at 12:50
• Brilliant proof. There are some mistakes of Latex of the exponents. – 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.