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