Enumerating large (20-digit) [probable] prime numbers

Question

Given A, on the order of 10^20, I'd like to quickly obtain a list of the first few prime numbers greater than A. OK, my needs aren't quite that exact - it's alright if occasionally a composite number ends up on the list.

What's the fastest way to enumerate the (probable) primes greater than A?

Is there a quicker way than stepping through all of the integers greater than A (other than obvious multiples of say, 2 and 3) and performing a primality test for each of them? If not, and the only method is to test each integer, what primality test should I be using?

Answer 1

Is there a quicker way than stepping through all of the integers greater than A (other than obvious multiples of say, 2 and 3) and performing a primality test for each of them?

No, there's no way of knowing if a number is prime without a primality test.

You can, however, perform a probabilistic primality test such as Miller-Rabin on any number very quickly. This is a safe and well accepted method of finding large primes. Since primes are relatively abundant, you'll have no trouble finding primes in any range using this method. Just use a tested and efficient Miller-Rabin implementation, and you'll be fine.

Answer 2

About the best you can do is generate a reasonable candidate, and then test it. The Miller-Rabin test meets your requirement of giving a high probability of the number being prime, and you can reduce the chance of a composite slipping through to a more or less arbitrary level depending on how many iterations you use.

Answer 3

Great question. This is still not proved to be in polynomial time (polynomial in the number of digits, here 20) — this was the Finding Primes Polymath project, where several mathematicians (including Fields Medallists Terence Tao and Tim Gowers!) tried to come up with an algorithm, but the project doesn't seem to have had any concrete results yet.

Anyway, there are several things you can do. One of them, as you and others have pointed out, is to try each number and check whether it's prime, with a fast primality test like Miller–Rabin. By well-known number-theoretic heuristics (based on the prime number theorem), the "probability" of a number near n being prime is around 1/ln(n), so with 10^20, about in every 46 numbers will be prime. So if you want k 20-digit numbers, you'll run the Miller-Rabin test on about 50k numbers.

The second approach, which I think might be faster if you're doing this for many many A's (haven't thought carefully) is to instead use a sieve, like the Sieve of Eratosthenes. If you want k primes, make an array with about 50k numbers (or more to be safe), and sieve through them. You'd start with a precomputed list of primes less than some number. (10¹⁰ to be perfectly correct, but since you're willing to tolerate some composite numbers, a smaller list of prime numbers will do, e.g. testing by the first 50 million primes, ensures your numbers have no prime factors below 982,451,653, and there aren't many of them.)

The third approach is to find someone else's implementation for this problem. :-) For example, there's a webpage that given a number, finds the next prime number or finds the next ten prime numbers. If you use it online it appears you'll have to copy them down by hand, but the source code is available too.

Answer 4

Primes are quiet frequent numbers. Frequency of primes is log(n) that mean that on average each 46th number is prime where n=10^20. That mean that checking each number for primality is not such overhead.