In the derivation of the Miller-Rabin Primality (or actually, "probably composite") test, Wikipedia http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test as well as other sites (including several Stack Exchange answers, as a lot of people have asked about this test) have a couple of small details that I am a bit stumped on. You start with the exponent p-1 in Fermat's Little Theorem (FLT) being odd, so after picking a < p, you express the a^(p-1) in FLT as a^[(2^s)d] for d odd, so sloppily using "=" as "equivalent", a^[(2^s)d]=1 mod p Taking square roots, we get a^[(2^(s-1))d]=+/- 1 mod p If s-1 > 0, we can take the +1 mod p and do it again, etc. until we run out of factors of 2. So far, so good. But here is my question. In the last step, Wiki (and everyone else) gets a^[(2^r)d]=-1 mod p for SOME r, -1 < r < s, OR a^d =1 mod p. But as far as I can see, a^[(2^r)d]=+/-1 for ALL -1 < r < s Why the exclusions?


For any prime $p$, it is true that $x^2 \equiv +1\pmod{p} \implies x \equiv \pm 1 \pmod{p}$ [*].

However it is not true that $x^2 \equiv -1\pmod{p} \implies x \equiv \pm 1 \pmod{p}$.

If you know that $a^{2^{r+1}d} \equiv +1\pmod{p}$, then by [*] you get $a^{2^rd} \equiv \pm 1 \pmod{p}$.

But, you can't say whether $a^{2^rd} \equiv -1 \pmod{p}$ or $a^{2^rd} \equiv +1 \pmod{p}$.

If it turns out that $a^{2^rd} \equiv -1 \pmod{p}$, then you can't use [*] to say anything about $a^{2^{r-1}d} \equiv -1 \pmod{p}$, and so, you have to stop the process at $a^{2^rd} \equiv -1 \pmod{p}$.

However, if it is the case that $a^{2^rd} \equiv +1 \pmod{p}$, then you can use [*] to get that $a^{2^{r-1}d} \equiv \pm1 \pmod{p}$, and the process continues on.

If we stopped the process at some $r$, $0 \le r \le s-1$, then we got that $a^{2^rd} \equiv -1 \pmod{p}$.

If this process continued on as long as it could, then at $r = 0$ we got $a^{d} \equiv +1 \pmod{p}$, and we stopped there since $d$ is odd.

This is why you can conclude that either $a^{2^rd} \equiv -1 \pmod{p}$ for some $r$, $0 \le r \le s-1$ or $a^d \equiv +1\pmod{p}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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