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.
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/pe
Z)*. 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
)) = w for both Wieferich primes w.
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.
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:
- w = 1093: 5654273717, 26092328809, 31310555641, 237865367741, 333967711897, 601401837037
- w = 3511: 129816911251, 259621495381, 346157884801, 12634325182441, 24273469559431, 57114029344321
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
> 1 coprime. Note that q1
for both Wieferich primes w.
- If q1 > q2 · w2, then n will be found in S(q1).
- If q1 < q2 · w2, then n will be found in S(q2 · w2).
With S(q) we denote the set of pseudoprimes found by the category S algorithm