Vtyjkyuk

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 $bin2, 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 $bleq 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 $bleq 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^dequiv 1 (mod n)$ or, for some $r$ with $0leq r < s$, $left(b^dright)^2^requiv -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.

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

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.

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

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

The deterministic version requires a modification as to how base values are handled. The base b is reduced mod n, and the test skipped (e.g., 'passed') in the event that b mod n = 0. More details here.

I have a working implementation here.