Return to Question

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+\epsilon})$ 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 algorithm" — this polite name is for algorithm 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.

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.

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+\epsilon})$ and degrades otherwise (say, sieve of Eratosthenes for interval $[N, N+1)$ is the same as method of trial division).

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+\epsilon})$ 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 algorithm" — this polite name is for algorithm 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.

What are the best known primality test 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+\epsilon})$ and degrades otherwise (say, sieve of Eratosthenes for interval $[N, N+1)$ is the same as method of trial division).

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+\epsilon})$ and degrades otherwise (say, sieve of Eratosthenes for interval $[N, N+1)$ is the same as method of trial division).