**
**

# Pseudoprimes

main page
database
statistics
verification
## Category E: n is not n^{1/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.