5
$\begingroup$

This webpage (as well as Wikipedia) explains how one can use the Miller-Rabin test to determine if a number in a particular range is prime. The size of the range determines the number of required bases to test. For example:

If $n < 9,080,191$ is a base $31$ and base $73$ strong probable prime, then $n$ is prime.

If $n < 2,152,302,898,747$ is a base $2, 3, 5, 7,$ and $11$ strong probable prime, then $n$ is prime.

How many bases must I test to deterministically tell if any integer $n < 2^{63}-1$ is prime?

As one may guess by the bound, I'm interested in using this approach for primality testing in programs. Assuming the truth of the extended Riemann hypothesis (which I'd be willing to do, given that I am using this code simply for competitions and/or "toy" problems, but not for high-risk applications), it is sufficient to test all bases $a$ in the range $1<a<2\log^2(n)$.

Reducing the number of bases I need to check could dramatically improve the runtime of my code; thus, I was wondering if there was a smaller number of bases.

$\endgroup$
3
  • 1
    $\begingroup$ You might consider using the Baillie Pomerance Selfridge Wagstaff test, which has no false positives below $2^{64}$ and typically should be faster than twelve strong Fermat tests. (Almost all non-primes will be found by the base-$2$ test already.) $\endgroup$
    – Daniel Fischer
    Commented Nov 3, 2014 at 21:29
  • 1
    $\begingroup$ @DanielFischer Thanks! I'll look at that test, too. The fact that the wiki page says "there are also no known composite numbers above $2^{64}$ that pass the test" is quite intriguing. $\endgroup$
    – apnorton
    Commented Nov 3, 2014 at 21:33
  • 3
    $\begingroup$ @anorton: There are believed to be infinitely many BPSW-pseudoprimes, but none have been found. See pseudoprime.com/pseudo.html and especially the Alford-Grantham list. $\endgroup$
    – Charles
    Commented Nov 3, 2014 at 23:50

2 Answers 2

Reset to default
10
$\begingroup$

According to A014233,

$a(12) > 2^{64}$. Hence the primality of numbers $< 2^{64}$ can be determined by asserting strong pseudoprimality to all prime bases $\leqslant 37 (= \text{prime}(12))$. Testing to prime bases $\leqslant 31$ does not suffice, as $a(11) < 2^{64}$ and $a(11)$ is a strong pseudoprime to all prime bases $\leqslant 31 (= \text{prime}(11))$. [Joerg Arndt, Jul 04 2012]

$$a(11) = 3825123056546413051 < 2^{62}$$

$\endgroup$
0
4
$\begingroup$

If, for some reason, you insist on only using the first n prime bases, then you need 12 bases for cover the 64-bit space. If you use some of the better sets people have found, then the best we know of is 7 (http://miller-rabin.appspot.com/) and depending on the input size you may be able to use fewer. If you're willing to use a 32k hash table, this can be brought down to 3. The BPSW test can be made to run in about the cost of 2.7x M-R tests and doesn't require the hash table.

My preference is to do a tiny bit of trial division (primes to 53, but some people like less), then 1 M-R if $n < 341531$, 2 M-R if $n < 1050535501$, otherwise BPSW. The AES Lucas variant using Montgomery math is fastest for me, but it's up to you -- standard, strong, extra strong, AES, and others have all been shown to work. Just make sure you test whatever you end up using.

$\endgroup$
2
  • $\begingroup$ Most compilers produce very fast code for checking divisibility of a 64 bit number by a constant, using two (fast) multiplications instead of a slow division and another multiplication. If you do the trial division with constants and not a loop using a table of primes, I would think it will be faster to go quite a bit beyond 53. $\endgroup$
    – gnasher729
    Commented Jun 9, 2016 at 23:46
  • $\begingroup$ @gnasher729, I do use constants, not a table. Flipping the issue around, the faster the primality tests, the less trial division one would want. I will note I moved to 89 for inputs over 32-bit, as well as using a single-base hashed M-R solution for 32-bit inputs. $\endgroup$
    – DanaJ
    Commented Jun 10, 2016 at 6:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .