Why is this deterministic variant of Miller-Rabin not working?

Question

I am using this paper as a reference.

The Miller-Rabin test, as classically formulated, is non-deterministic -- you pick a base $b$, check if your number $n$ is a $b$-strong probable prime ($b$-SPRP), and if it is, your number is probably prime (repeat until "confident.")

A deterministic variant, assuming your number $n$ is below some bound (say $n<2^{64}$), is to pick a small number of bases $b$, and check if $n$ is a $b$-SPRB relative to each of those bases. There seems to be a bit of a sport to finding very small sets of bases, so as to make this process as fast as possible.

In particular, the cited reference declares a theorem of Jaeschke and Sinclair, that

If $n < 2^{64}$ is a $b$-SPRP for $b\in\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}$, then $n$ is a prime.

It doesn't state any extra hypotheses on $n$, or on what it means to be a $b$-SPRP. However, the classical formulation of Miller-Rabin only talks about $n$ being a $b$-SPRP when $b\leq n-2$, whereas the theorem above seems to allow $n<b$.

In particular, I have found (purely by accident) that $n=13$ does not satisfy the above criterion, meaning that as stated it gives wrong answers, and I don't know why (so I can't predict more of them).

So the question: Is this a shortened form of a proper theorem, where I should only be checking the values of $b$ where $b\leq n-2$? Is this an error in the paper? Am I just crazy?

For sake of completeness, the definition of $b$-SPRB I am using is the one given in the paper:

Factor $n$ as $2^sd$, where $s$ and $d$ are nonnegative integers and $d$ is odd. Then $n$ is a $b$-SPRB iff $b^d\equiv 1\ (mod\ n)$ or, for some $r$ with $0\leq r < s$, $\left(b^d\right)^{2^r}\equiv -1\ (mod\ n)$.

---

Not a duplicate of: Bases required for prime-testing with Miller-Rabin up to $2^{63}-1$ seems to lead to the same questions (they don't address the issue of when $n<b$; it's just irrelevant there) and uses bases so small it doesn't matter.

Answer 1

As stated the theorem is fine, because it only says if $n$ is a $b$-SPRB for all these $b$ then it is prime; it does not say "if and only if".

A prime $p$ will be a $b$-SPRB for any base $b$ which is not a multiple of $p$. So every prime will pass the test except for primes dividing one of the bases listed. Those primes are $2, 3, 5, 13, 19, 73, 193, 407521$ and $299210837$.

Answer 2

Sometimes the definition of SPRB includes the condition $\gcd(b,n)=1$. Anyway, if $b$ is a multiple of $n$ you have $b^d\equiv 0 \pmod n$ and $n$ cannot be a b-SPRB. So your implementation of the test is not correct, because $325 = 25\times13.$

And you should always do the simple test $\gcd(n,b)=1,$ if it fails you know $n$ is composite.

Answer 3

If you look at Best known SPRP base sets, you can see the remark "Depending on your Miller-Rabin implementation, you may need to take a ← a mod n." and "When the witness a equals 0, the test should return that n is prime." The latter is saying we skip that test when n divides the base.

This is especially critical for making sense of the smaller base sets which generally have very large bases.