2
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$
    – Geoffrey Irving
    Jul 12, 2020 at 14:19
  • $\begingroup$ @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. $\endgroup$
    – user1123502
    Jul 12, 2020 at 14:24
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Jul 12, 2020 at 16:28
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Jul 13, 2020 at 15:53
  • $\begingroup$ I'm thinking of a GPU version of an algorithm based on 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. $\endgroup$
    – Gerhard Paseman
    Jul 13, 2020 at 16:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.