Category S: n is n1/2-smooth
We want to enumerate pseudoprimes which have no 'large' prime factor. More precisely: enumerate all pseudoprimes n with no prime factor larger than n1/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 n1/2
. We only need to consider q ≤ x2/3
, the proof follows.
Assume we have a pseudoprime n' = q' · s' in S with q' > x2/3
. We can write q' = q1
. This gives us q1
. We only consider n' ≤ x, so we have s' < x1/3
and s' · q2
. This shows that this pseudoprime will be found for either q = s' · q2
or q = q1
, whichever is the largest, concluding the proof.
Writing q = q1
, it suffices to only consider q1
, since small factors from q1
can be transferred to q2
. Proof: suppose q1
, and write q1
. The smoothness condition yields we can take both q1a
. Furthermore, one of both (let's say q1b
) is smaller than x1/3
. Then q2
, proving the assertion.
Another useful restriction is gcd(q1
) = 1. This enables easy computation of rho(q) = lcm(rho(q1
)). The problem with this restriction, is that some
nonsquarefree pseudoprimes will be missed. These pseudoprimes are gathered in a special search
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 [qlo
] 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 = q1
coprime. When gcd(q2
)) > 1, then we can discard all multiples of q2
since they will fail the gcd condition also. We only consider gcd(q1
) = 1 because this allows us to use rho(q) = lcm(rho(q1
)). 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 ≤ x2/3
in many ways.
After a week of running on 8 cores of SI01 and some postprocessing, this category has been completed.