# Conditions that suffice to show compositeness using Miller-Rabin test

I'm trying to sort out two descriptions of the Miller-Rabin test for primality: the one from Rabin's original paper and that from Wikipedia's article.

Let $n$ be the number we wish to test, and let $a \in \mathbb{Z}/n\mathbb{Z}$. Assuming $n$ is odd, we can write $n - 1 = 2^s d$, where $d$ is odd.

Wikipedia's description states that if:

1) $a^d \not\equiv 1 \text{ mod } n$, and

2) there is no $r\in \{0,1,s-1\}$ such that $a^{2^rd}\equiv -1 \text{ mod } n$,

then $n$ is composite.

Rabin's article — and here I'll modify his formulation (p. 130) a bit, to make it comparable to the above — states that if:

1') $a^{n-1} \not\equiv 1 \text{ mod } n$, or

2') there exists $r\in\{0,1,s-1\}$ such that $1<(a^{2^rd}-1,n)<n$,

then $n$ is composite.

In each case the path from premise to conclusion makes sense to me. What I don't get is: Why two different descriptions? Presumably, they're equivalent. If so, why?

One difference lies in the conjunctions: Since Wikipedia's description requires that two conditions be met, it would seem easier to show that they do not hold. (Well, sort of: $a^d \equiv 1$ less often than $a^{n-1} \equiv 1$.) The or in Miller's conditions almost seem to relax the requirements — a relaxing that, I'd assume, is actually not happening. So how does that work — going from two conditions to one?

The reader might take issue with the direction suggested in the preceding question: Rabin came first, of course. But I find Wikipedia's presentation a lot more intuitive; the motivation behind the conditions is clear. I don't find this to be true for Rabin's conditions.

In particular, I have no idea where his second condition comes from. I know that $(a^{2^rd}-1,n)=(n,a^{2^rd}-1\text{ mod }n)$, but beyond this trivial observation, I have no insight. So where does it come from? Obviously, if the gcd of $n$ and anything has the stated bounds, then $n$ is composite. But why pick $a^{2^rd}-1$? The only benefit I can see is that there's a smaller number of such terms (viz $s$) than those that match the description of "anything" (less than $n$, of course).

• One often calls $a$ a "witness" to the compositeness of $n$ iff the strong pseudoprime test for $n$ using (exponential) base $a$ fails. Your subject line suggests a focus on the sufficiency of some such test (finding a witness) in the Miller-Rabin primality test when $n$ is composite. Perhaps more interesting is the converse aspect, of showing a witness can necessarily be found. – hardmath Nov 29 '15 at 16:59