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 = 264-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) = 2r - 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.