View Single Post
Old 2021-08-28, 06:15   #46
Mar 2021

53 Posts

This might work ...
If n is a 2-psp (pseudoprime to base 2) and prime p divides n then
n = p, mod (p*ord(p))
where ord(p) is the multiplicative order of 2 mod p

This can be used to sieve for numbers that are possible 2-psp. ord(p) is usually about as large as p so the product is ~p2. This makes the psp-sieve much faster than a regular sieve.

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.

I think this will be faster than SPRP + Lucas.

Any thoughts?
CraigLo is offline   Reply With Quote