View Single Post
Old 2021-09-03, 16:01   #48
ATH's Avatar
Dec 2003

2×3×13×41 Posts

Originally Posted by CraigLo View Post
The algorithm:
1. Find all primes up to sqrt(N) = 232.5 if we want to check up to 265.
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 psp-sieve 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 264 to 265. For these we could precompute a list of possible 2-psp instead of sieving.

5. Fermat test.
If you sieve to sqrt(N) you can use a normal sieve, you do not need psp-sieve 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*106)2.

Last fiddled with by ATH on 2021-09-03 at 16:07
ATH is offline   Reply With Quote