**
**

# Pseudoprimes

main page
database
statistics
verification
## Category S: n is n^{1/2}-smooth

### Main strategy

We want to enumerate pseudoprimes which have no 'large' prime factor. More precisely: enumerate all pseudoprimes n with no prime factor larger than n

^{1/2}. The idea is to form pairs (q, rho(q)), for each pair iterating over all s < q, s = q

^{-1} mod rho(q), testing if n = q · s is a pseudoprime.

### Search restrictions for q

As normally, we write n = q · s with 1 < s ≤ q both odd. The smoothness condition gives us that

**q is composite** and has no prime divisors exceeding n

^{1/2}. We only need to consider

**q ≤ x**^{2/3}, the proof follows.

Assume we have a pseudoprime n' = q' · s' in S with q' > x

^{2/3}. We can write q' = q

_{1} · q

_{2} with q

_{2} ≤ q

_{1} ≤ x

^{1/2}. This gives us q

_{1} > x

^{1/3}. We only consider n' ≤ x, so we have s' < x

^{1/3} and s' · q

_{2} < x

^{2/3}. This shows that this pseudoprime will be found for either q = s' · q

_{2} or q = q

_{1}, whichever is the largest, concluding the proof.

Writing q = q

_{1} · q

_{2}, it suffices to only consider q

_{1} ≤ x

^{1/2}, since small factors from q

_{1} can be transferred to q

_{2} if q

_{1} exceeds x

^{1/2}. Proof: suppose q

_{1} > x

^{1/2}, and write q

_{1} = q

_{1a}q

_{1b}. The smoothness condition yields we can take both q

_{1a}, q

_{1b} ≤ x

^{1/2}. Furthermore, one of both (let's say q

_{1b}) is smaller than x

^{1/3}. Then q

_{2} · q

_{1b} ≤ x

^{1/2}, proving the assertion.

Another useful restriction is gcd(q

_{1}, q

_{2}) = 1. This enables easy computation of rho(q) = lcm(rho(q

_{1}), rho(q

_{2})). The problem with this restriction, is that

*some* nonsquarefree pseudoprimes will be missed. These pseudoprimes are gathered in a

special search.

### Algorithm

The entire 32 bit

rho table is loaded into memory. This requires 8GB of memory, so the program should be run on a suitable machine.

We split the q range into 69815 blocks [q

_{lo}, q

_{up}] of 50 million odd q each. For each block we first tabulate pairs (q,rho(q)) during the so-called

*prefill phase*.
The prefill phase constructs composite q = q

_{1} · q

_{2}, q

_{1} > q

_{2} coprime. When gcd(q

_{2}, rho(q

_{2})) > 1, then we can discard all multiples of q

_{2} since they will fail the gcd condition also. We only consider gcd(q

_{1}, q

_{2}) = 1 because this allows us to use rho(q) = lcm(rho(q

_{1}), rho(q

_{2})). At the end of the prefill phase, which generally takes about 30 seconds per block on the SI01 machine, this generally yields 33 to 49% of pairs to work with.

For each pair (q, rho(q)) we construct and test pseudoprime candidates by iteration over s. The number of s to test is quite large for the lower 100 blocks, but decreases rapidly for increasing q. For every q a modular inverse must be computed, requiring about 10 seconds per block. We again discard some

nonsquarefree pseudoprimes taking gcd(q, s) = 1, because this enables easy computation of rho(n) which is used to test n on pseudoprimality.

The output of this algorithm gives very many duplicate pseudoprimes, because most pseudoprimes can be written as q · s with s < q ≤ x

^{2/3} in many ways.

### Results

After a week of running on 8 cores of SI01 and some postprocessing, this category has been completed.