17
$\begingroup$

For very small numbers, say 32 bits unsigned, testing all divisors up to the square root is a very decent approach. Some optimizations can be made to avoid trying all divisors, but these yield marginal improvements. The complexity remains $O(\sqrt n)$.

On the other hand, much faster primality tests are available, but they are pretty sophisticated and deploy their efficiency for much longer numbers.

Is there an intermediate solution, i.e. a relatively simple algorithm, that is of practical use for, say, 64 bits unsigned, with a target running time under 1 ms ?

I am not after micro-optimization of the exhaustive division method. I am after a better working principle, of a reasonable complexity (and of the deterministic type).


Update:

Using a Python version of the Miller-Rabin test from Rosetta code, the time for the prime $2^{64}-59=18446744073709551557$ is $0.7$ ms. (Though this is not a sufficient test because nothing says we are in a worst case.)

http://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Python:_Proved_correct_up_to_large_N

And I guess that this code can be improved for speed.

$\endgroup$
14
  • $\begingroup$ You can build a sieve filtering out multiples of any primes you have already tried as you go. But it will of course require more memory to keep track of. $\endgroup$ Oct 20, 2017 at 8:37
  • 2
    $\begingroup$ @Zubzub: for a prime close to 2^64, the function will try close to 2^32 divisions, so no. (By the way, for 18446744073709551557 it takes six minutes). $\endgroup$
    – user65203
    Oct 20, 2017 at 8:38
  • 2
    $\begingroup$ @mathreadler: I doubt this is usable for 64 bit integers. And if I am right, the gain will not exceed a factor log(n), not counting overhead. $\endgroup$
    – user65203
    Oct 20, 2017 at 8:40
  • 1
    $\begingroup$ $1$ second is absolutely no proeblem. Even $100$-digit numbers can be proven to be prime with PARI/GP using the Adleman-Pomerance-Rumely-test within about $200$ milliseconds. But $1ms$ ? Perhaps the BPSW-test is a good idea, which is correct upto at least $2^{64}$. Trial division makes only sense, if we want to test many numbers, to reduce the number of candidates, but verifying $64$-bit numbers via trial division actually is not efficient. But checking the first few primes (lets say upto $100$) could slightly improve the test. $\endgroup$
    – Peter
    Oct 20, 2017 at 10:51
  • 1
    $\begingroup$ A deterministic implementation with a maximum of 7 base tests, here. $\endgroup$
    – Brett Hale
    Sep 5, 2018 at 9:33

2 Answers 2

16
$\begingroup$

I think some version of the (deterministic) Miller-Rabin Test should do the trick. It is usually used as a probabilistic test for whopping big numbers, but it can be repurposed as a deterministic test for smaller fixed ranges.

The core of the Miller-Rabin test is the notion of a "probable prime" for some base $a$. Specifically, let $n$ be an odd prime, and write $n - 1 = d \times 2^s$ for some odd $d$. Then, it follows that $a^d \equiv 1 \pmod{n}$ or $a^{d 2^r} \equiv -1 \pmod{n}$ for some $0 \leq r < s$. (The wikipedia page has reasoning for this).

If $n$ is any number, and $a<n$, we could run the same test, and if that test passed we would call $n$ a strong pseudoprime for base $a$. The usual Miller-Rabin test is based on doing this for a lot of different (randomly chosen) $a$, and some number-theoretic argument saying that if $n$ is composite, the probability of not finding an $a$ demonstrating this is vanishingly small (after trying a lot of them).

However, if Wikipedia is to be believed (I haven't followed up the reference), then for $n < 2^{64}$ it is sufficient to test $a \in \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$. Somehow there are no composite numbers below $2^{64}$ which are a strong pseudoprime for all these $a$.

The above test is very fast, and altogether prime testing would require at most $12 \times 64$ modular exponentiations (this will be well below 1ms). For smaller $n$, you could even use a smaller list of possible $a$'s.

$\endgroup$
7
  • $\begingroup$ I guess that this is exactly what I was looking for: nice tradeoff between complexity and efficiency. $\endgroup$
    – user65203
    Oct 20, 2017 at 11:01
  • $\begingroup$ @YvesDaoust For so small numbers, the adleman-pomerance-rumely-test is not much slower (even with the slow program PARI/GP on my also slow computer $64$-bit digit-.numbers require less than $1$ millisecond for a decision. $\endgroup$
    – Peter
    Oct 20, 2017 at 11:12
  • $\begingroup$ @Peter: The only description of that algorithm I can find goes for pages and pages though. It doesn't look "relatively simple". The algorithm I described I can implement in about 20 lines of Python. $\endgroup$
    – Joppy
    Oct 20, 2017 at 11:24
  • 3
    $\begingroup$ @JiK: Well, I meant reasonably. In another language like C, you might have to write your own modular exponentiation, but that's about it. $\endgroup$
    – Joppy
    Oct 20, 2017 at 11:58
  • 4
    $\begingroup$ According to miller-rabin.appspot.com, it is sufficient to run the Miller–Rabin test for $a\in\{2,325,9375,28178,450775,9780504,1795265022\}$; that’s 7 trials instead of 12. $\endgroup$ Oct 20, 2017 at 15:53
10
$\begingroup$

oeis/A014233 says:

The primality of numbers $\lt 2^{64}$ can be determined by asserting strong pseudoprimality to all prime bases $\le 37$.

The reference is the recent paper Strong pseudoprimes to twelve prime bases by Sorenson and Webster.

For code, see Prime64 and also the primes programs in FreeBSD, especially spsp.c.

$\endgroup$
3
  • $\begingroup$ This is true, but depends on previous work (i.e. somebody has already checked this works). Does that make it any different to downloading a list of primes? $\endgroup$
    – Henry
    Oct 20, 2017 at 10:36
  • 3
    $\begingroup$ @Henry, yes, because the list is too long. The OP only wants to test, not to list. $\endgroup$
    – lhf
    Oct 20, 2017 at 10:37
  • $\begingroup$ @Henry: lhf is right. I am looking for an algorithm that avoids usage of big tables. $\endgroup$
    – user65203
    Oct 20, 2017 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy