Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
What don't you understand about the explanation at the Wikipedia article, which also includes examples? –  Qiaochu Yuan Sep 14 '10 at 5:09
3  
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. 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. Sep 14 '10 at 6:41
add comment

4 Answers

up vote 16 down vote accepted

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

share|improve this answer
    
+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
2  
@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
add comment

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.

share|improve this answer
1  
I'm sorry - I don't understand much of that. –  Smashery Sep 14 '10 at 6:35
1  
@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. –  Bill Dubuque Sep 15 '10 at 1:35
1  
I'd give this a second vote if I could. –  Charles Dec 11 '10 at 1:38
add comment

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.

share|improve this answer
1  
Caution the result fails for p = 2 since 1 = -1 yields only 1 root. –  Bill Dubuque 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. 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. Sep 14 '10 at 6:39
2  
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
show 1 more comment

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")

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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