Pseudoprimes
main page
database
statistics
verification
Category E: n is not n1/2-smooth
Search strategy
Each pseudoprime n in this category has a large prime divisor p and a smaller cofactor s. If we write r =
rho(p), then s ≥ r + 1 (because s = 1 mod r), hence p ≤ x / (r+1) with x = 2
64-1. For odd r, we can improve the bound on p since the smallest s candidate is 2r+1: p ≤ x / (2r+1).
Given pairs (r,p), the associated pseudoprimes can be easily computed by iteration over s and testing if p*s mod rho(s) = 1.
All primes p with fixed r = rho(p) follow from the factorization of the
Mersenne number M(r) = 2
r - 1. For r < 859 all Mersenne factorizations are complete. Beyond that, factorizations are tracked by
Will Edgington and
www.factordb.com.
The main computational work went into this search: tens of CPU years. Even though for small Mersenne numbers the ECM efforts would make it practically impossible that small factors would be found by trial division, those numbers were tested by trial division anyway. All factors found were submitted to factordb and GIMPS (TODO check?).
Special thanks go to Geoff Reynolds for his optimized assembly implementations of
modular exponentation, which
greatly sped up computations.