2

What are the best known primality test(s) for the whole intervals of integers up to $N=10^{20}$ ? "Best" means "have minimal amortized time per tested integer".

That is, the algorithm(s) should be fast only when testing a whole interval of integers. Just like sieve of Eratosthenes works well only if we test all integers in the whole interval $[N, N+N^{1/2+\varepsilon})$ and degrades otherwise (say, sieve of Eratosthenes for interval $[N, N+1)$ is the same as method of trial division).

UPDATE:

The question probably should be asked as "What is the best prime generation algorithm for modern computer hardware for integers up to $10^{20}$

Then for the modern CPU the answer probably is "cache-friendly prime generation algorithms" — this polite name is for algorithms that workaround severe non-randomness access time to modern RAM. There should be answer for modern GPGPU too.

I still expect that somebody will answer, not me.

user1123502
  • 121
  • 3
  • 1
    Just a comment since this is a point test rather than an amortized test, but in case it’s useful for others: Michal Foriˇsek and Jakub Janˇcina, Fast Primality Testing for Integers That Fit into a Machine Word. – Geoffrey Irving Jul 12 '20 at 14:19
  • @GeoffreyIrving Sometimes it may be possible to modify point test into amortized test, just like trial division test may be modified into the sieve of Eratosthenes and have some perfomance gain. But, of course, I am more interested in the "ready to use" tests. – user1123502 Jul 12 '20 at 14:24
  • Wheel sieving is ready to use. You might find that in combination with some other tests useful. Gerhard "Sometimes Settles For Pretty Good" Paseman, 2020.07.12. – Gerhard Paseman Jul 12 '20 at 16:28
  • 2
    Since you have roughly 10^18 primes with 20 decimal digits, what are you going to do with them? Gerhard "Please Don't Print Them Out" Paseman, 2020.07.13. – Gerhard Paseman Jul 13 '20 at 15:53
  • I'm thinking of a GPU version of an algorithm based on https://mathoverflow.net/q/243490 . You can add a comment there if you are interested and would like to contribute. Gerhard "Is Going For Gentle Solicitation" Paseman, 2020.07.13. – Gerhard Paseman Jul 13 '20 at 16:02
  • Primesieve is good in practice: https://github.com/kimwalisch/primesieve – Max Alekseyev Jul 14 '20 at 10:09
  • @GerhardPaseman 1. Wheel sieving is useful, but not a simple thing: it is cache unfriendly, at least by naive implementation. 2. It may be possible to use 10^18 primes to estimate, say, Brun's constant more precisely. And 10^20 is upper limit. 3. GPU version is interesting, but I still do not understand GPU programming (but plan to learn it sometimes). BTW, the sieve of Eratosthenes seems to be GPU unfriendly due to demand for random writes and big cache size. I shall carefully read your question mathoverflow.net/q/243490 – user1123502 Jul 17 '20 at 10:46
  • @MaxAlekseyev For now this primesieve looks like the best know practical sieve. But I suspect that good algorithm will be 10 times faster for primes starting from $10^{15}$, at least on processors like x5-Z8350. – user1123502 Jul 17 '20 at 10:50
  • @MaxAlekseyev I still have not tested it on processors with big cache size. – user1123502 Jul 17 '20 at 11:01

0 Answers0