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