1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the clarification. $\endgroup$ – Richard Rast Aug 31 '17 at 14:39
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.