|
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 Cheers! |
|||||||||||
|
|
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 |
|||||||
|
|
Below is little-known general yet simple answer to your question about nontrivial sqrts $\rm (mod\ m)\:$. THEOREM $\;$ One may quickly factor $\rm m>1\:$ given a polynomial with more roots mod $\rm\: m\:$ than its degree, viz. suppose that, modulo $\rm m,\;$ the polynomial $\rm\: f(x)\ne 0\:$ has degree $\rm\:n\:$ but has $\rm\:n+1 \:$ distinct roots $\rm\:r_{\:i}\:$. Then one of $\rm\;gcd(m\;,\:r_{\:i} - r_{\:j}\:),\; i\ne j \:$ must yield a proper factor of $\rm\:m\;$. For if that failed, then all of the gcds must be improper so $1\:,\:$ not $\rm\;m \;$ since $\rm\; i\ne j\;\Rightarrow\; r_{\:i}\: \not\equiv r_{\:j}\ (mod\ m) \:$. Now an induction using the Factor Theorem yields $\rm\;f(x) = (x-r_1)\cdots(x-r_{n+1})\; g(x),\;\; g(x) \ne 0 \;\;$ contra $\rm\;\:\deg\: f = n \;$. EXAMPLE $\rm\;(deg\ f = 1)\;\:$ Suppose, modulo $\rm\:m\:$, that $\rm\; 0 \:\ne\: f \:=\: a\:x\;$ has a "nontrivial" root $\rm\: b\ne 0\:$. Then $\:\rm gcd(m,b)\:$ is a proper factor of $\rm\: m\:.\ $ More directly: $\rm\; m\:|\:ab\:,\;$ not $\rm\; m|a\;\:$ nor $\rm\: m|b \;\Rightarrow\; gcd(m,b)\;$ is a proper factor of $\rm\:m\:,\:$ i.e. if $\rm\: m\:$ fails the Prime Divisor Property then $\rm\: m\:$ is "constructively" composite. EXAMPLE $\rm\;(deg\ f = 2)\;\:$ Suppose, modulo $\rm\:m\:$, that $\rm\; x^2 = 1\;$ has a "nontrivial" square root $\rm\: b\ne \pm1\:$. Then $\;\rm gcd(m,b\pm 1)\;$ yields a proper factor of $\rm\: m\:$ when $\rm\: m\:$ is odd. This idea lies at the heart of many integer factorization algorithms. The above proof easily extends to yield a proof of the following THEOREM $\ $ Ring $\rm\: R\:$ is a domain $\iff\:$ every $\rm 0 \ne 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\; a \ne 0\;$ then the polynomial $\rm\: a\:x\:$ has only the root $\rm\; x = 0\:,\:$ hence $\rm\ ab = 0 \ \Rightarrow\ b = 0\:,\:$ therefore $\rm\: R\:$ has no zero divisors. |
|||||||||||||
|
|
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. |
|||||||||||||||
|
|
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:
|
|||||
|
