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$
  • $\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$ – mathreadler Oct 20 '17 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$ – Yves Daoust Oct 20 '17 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$ – Yves Daoust Oct 20 '17 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 '17 at 10:51
  • 1
    $\begingroup$ A deterministic implementation with a maximum of 7 base tests, here. $\endgroup$ – Brett Hale Sep 5 '18 at 9:33
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$
  • $\begingroup$ I guess that this is exactly what I was looking for: nice tradeoff between complexity and efficiency. $\endgroup$ – Yves Daoust Oct 20 '17 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 '17 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 '17 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 '17 at 11:58
  • 3
    $\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$ – Emil Jeřábek supports Monica Oct 20 '17 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$
  • $\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 '17 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 '17 at 10:37
  • $\begingroup$ @Henry: lhf is right. I am looking for an algorithm that avoids usage of big tables. $\endgroup$ – Yves Daoust Oct 20 '17 at 10:59

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.