Quote:
Originally Posted by CraigLo
The algorithm:
1. Find all primes up to sqrt(N) = 2^{32.5} if we want to check up to 2^{65}.
2. Precompute ord(p) for all primes.
3. Use regular sieve with small primes. I currently use ~10k primes which is probably a good starting point. This greatly reduces the number of potential primes that need to be checked with a fermat test.
4. Use the pspsieve with all remaining primes. This guarantees that a number is prime if it passes the fermat test and isn't removed by either sieve. This should be fast because p*ord(p) >> p. In many cases p*ord(p) will be so large that it will only occur a few times in the interval 2^{64} to 2^{65}. For these we could precompute a list of possible 2psp instead of sieving.
5. Fermat test.

If you sieve to sqrt(N) you can use a normal sieve, you do not need pspsieve or Fermat test? Everything remaining will be prime.
I was thinking of another idea:
When you jump ahead, for example from p to p+1300, and test backwards until you find a PRP, then what about testing backwards until you have found 2 PRPs? (If first PRP found is still larger than p).
Most of the time those 2 PRPs will be found above p+1000 probably, and in case you get back to p in 2 PRPs and find a false gap, it will be double checked afterwards anyway.
At the price of 2 Fermat tests (+ any tests that are negative), we get a very low risk of missing a prime gap. What are the odds of finding 2 real PRPs so close together blocking a record prime gap? Probably near the square of the probability you calculated earlier? 1 in (8*10
^{6})
^{2}.