Enumeration of large (20-digit) [possible] primes

Question

Given A, of the order of 10 ^ 20, I would like to quickly get a list of the first few prime numbers, large A. OK, my needs are not entirely accurate - it is good if the number sometimes ends in the list.

What is the fastest way to list (probable) numbers greater than A?

Is there a faster way than overcoming all integers greater than A (different from the obvious multiples of, say, 2 and 3) and performing a conformance test for each of them? If this is not the case, and the only method is to check every integer, what should I use to verify the correctness?

Answer 1

Great question. This has not yet been proved in polynomial time (polynomial in the number of digits, there are 20 here) - it was the “ Polymath Project Search” , where several mathematicians (including field polarists Terence Tao and Tim Gowers!) Tried to develop an algorithm, but the project, does not seem to have any concrete results yet.

Anyway, there are a few things you can do. One of them, as you and others have noted, is to try each number and check if it is simple, with a quick criterion of strength, for example Miller-Rabin . According to the well-known number-theoretic heuristic (based on the prime number theorem ), the "probability" of a number near n is prime 1 / ln (n), so for 10 ^ 20, approximately every 46 numbers will be first. Therefore, if you want k 20-digit numbers, you will conduct a Miller-Rabin test for approximately 50 thousand numbers.

The second approach, which, in my opinion, can be faster if you do this for many many A (without thinking), should instead use a strong sieve, such as the Eratosthenes sieve . If you want k primes, make an array of about 50 thousand (or more to be safe) and sift them. You should start with a pre-computed list of primes smaller than some number. (10 ¹⁰ to be completely correct, but since you are ready to endure some compound numbers, making a smaller list of primes, for example, testing the first 50 million primes , ensures that your numbers do not have major factors below 982 451 653, and they are not so much.)

The third approach is to find another implementation for this problem. :-) For example, there is a web page that contains a number, finds the next prime number, or finds the next ten primes . If you use it online, you will need to copy them manually, but the source code is also available.

Answer 2

Is there a faster way than stepping through all integers greater than A (except for obvious multiples of say 2 and 3) and performing a primitive test for each of them?

No, there is no way to know if a number is prime without a conformance test.

However, you can very quickly perform a probabilistic strength test, such as Miller-Rabin . This is a safe and well-known method for finding large primes. Since primes are relatively large, it’s easy for you to find primes in any range using this method. Just use the proven and efficient Miller-Rabin implementation and everything will be fine.

Answer 3

The best thing you can do is create a reasonable candidate and then test it. The Miller-Rabin test satisfies your requirement of high probability that the number is prime, and you can reduce the likelihood that the composition will slide to a more or less arbitrary level depending on how many iterations you use.

Answer 4

Simple, quiet, frequent rooms. The prime frequency is log (n), which means that on average every 46th number is prime, where n = 10 ^ 20. This means that checking each number for primitiveness is not an overhead.