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.