Pseudoprimes

main page    database    statistics    verification   

W search: non-squarefree pseudoprimes

In the category S search algorithm, we used coprime factors for easy rho computations. However, this causes some pseudoprimes to be missed. On this page we will investigate how to correct the problem.

Wieferich primes

If a pseudoprime n is divisible by a square p2, then p is a Wieferich prime. Proof: write n = pe · m, such that e ≥ 2 and p does not divide m. Let k be the order of 2 in G = (Z/peZ)*. We have that k | n-1, and also k divides |G| = pe-1(p-1). This implies that p cannot divide k, hence k | p-1, giving 2p-1 = 1 mod pe. We conclude that p is a Wieferich prime.

The only known Wieferich primes are 1093 and 3511. There may be larger Wieferich primes, but not below x1/2, which is the range that concerns this project. We can now list the non-squarefree pseudoprimes.

Only squares, no cubes

There exist no 64-bit pseudoprimes which are divisible by a cube, because gcd(w3, rho(w3)) = w for both Wieferich primes w.

No cofactor

Both n = 10932 and n = 35112 are pseudoprimes. Because they are not found by both search algorithms, we need to add them to the result list ourselves.

Prime cofactor

If n = w2 · p with p prime, then the category E search will find all of these n for p > w2. We need to search p < w2 separately. This gives the following pseudoprimes:

Composite cofactor

Because the category E search does not miss any of these pseudoprimes, we only need to look at n in S.
Write n = w2 · q, q = q1 · q2 with q1 > q2 > 1 coprime. Note that q1 < x2/3 because q2 · w2 > x1/3 for both Wieferich primes w.
With S(q) we denote the set of pseudoprimes found by the category S algorithm at q.