Definition: Let $n$ be an integer with $n > 2$ and $n − 1 = 2^st$, where $s$ is a non-negative integer and $t$ is an odd positive integer. We say that $n$ passes Miller’s test for the base $b$ if either $b^t ≡ 1 \ ( mod \ n)$ or $b^{2^jt} ≡ −1 \ (mod \ n)$ for some $j$ with $0 ≤ j ≤ s − 1$.

I'm a bit confused with this. I thought the test was based on the fact if $x^2 - 1 \equiv 0 \ (mod \ p)$, then $x \equiv 1$ or $x \equiv -1$. If at any point we get $b^{2^jt} \not ≡ −1$ or $1$, shouldn't the test fail there? The test seems to say, you will constantly divide the exponent by 2 until you are left with just the odd integer $t$. If you at any point encounter a congruence to $-1 \ (mod \ n)$ before the $b^t$ case, you pass the test. If left with $b^t$ test and you get not congruent to $1$, you fail. What is the significance too, of $b^t$ being congruent to $1$ and not $-1$?

I apologize if the information is easily searchable. When I tried looking this up, I mainly found the Miller-Rabin test, which I think is a bit different from this. Thanks!

  • 1
    $\begingroup$ The Miller-Rabin test is just Miller's test with $b$ chosen at random. $\endgroup$ – Misha Lavrov Dec 8 '18 at 6:28
  • $\begingroup$ Oh... I'll take a look at it then, thank you very much. $\endgroup$ – Stawbewwy Dec 8 '18 at 6:29

The sequence $$ b^t \bmod n, b^{2t} \bmod n, b^{4t}\bmod n, \dots, b^{2^s t}\bmod n $$ should fail the test if, at any point in the sequence, we find a number that's not $-1$ (or $n-1$ if you prefer), followed by $1$. This gives us an $x \not\equiv \pm 1\pmod n$ whose square is $x^2 \equiv 1 \pmod n$, ultimately leading to a nontrivial factor of $n$. It should also fail if we don't get $1$ at the end; in that case, $n$ is not prime by the converse of Fermat's little theorem.

The alternative to the above is that

  • the sequence is entirely $1,1,1,\dots,1,1$, or
  • it ends with $\dots, -1, 1, \dots, 1,1$.

The first case is the one where $b^t \equiv 1 \pmod n$. In the second case, even if the sequence has elements other than $\pm 1$, that's fine, as long as they're before the $-1$. Seeing such elements doesn't tell us that $n$ is composite, because even for prime $n$, we don't really know what square roots of $-1$ look like.

  • $\begingroup$ I get it now I think. If what I looked up is correct, the only solutions to $x^2 \equiv 1 \ (mod \ p)$ are $1,-1$, so, it's possible to get $-1$ through other squares, but not $1$. Thank you very much for the post, it helped make things very clear for me :) $\endgroup$ – Stawbewwy Dec 8 '18 at 7:46
  • $\begingroup$ Yep, what you are saying is exactly correct. Glad I could help! $\endgroup$ – Misha Lavrov Dec 8 '18 at 17:14

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.