Pseudoprimes

main page    database    statistics    verification   

Category S: n is n1/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 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 · q2 with q2 ≤ q1 ≤ x1/2. This gives us q1 > x1/3. We only consider n' ≤ x, so we have s' < x1/3 and s' · q2 < x2/3. 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 · q2, it suffices to only consider q1 ≤ x1/2, since small factors from q1 can be transferred to q2 if q1 exceeds x1/2. Proof: suppose q1 > x1/2, and write q1 = q1aq1b. The smoothness condition yields we can take both q1a, q1b ≤ x1/2. Furthermore, one of both (let's say q1b) is smaller than x1/3. Then q2 · q1b ≤ x1/2, proving the assertion.

Another useful restriction is gcd(q1, q2) = 1. This enables easy computation of rho(q) = lcm(rho(q1), rho(q2)). 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 [qlo, qup] 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 · q2, q1 > q2 coprime. When gcd(q2, rho(q2)) > 1, then we can discard all multiples of q2 since they will fail the gcd condition also. We only consider gcd(q1, q2) = 1 because this allows us to use rho(q) = lcm(rho(q1), rho(q2)). 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.

Results

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