Category E: n is not n1/2-smooth
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
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.