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!

Solution 1:

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

Solution 2:

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$.

Solution 3:

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.