In 2002, William Galway
compiled a complete list
of base-2 Fermat pseudoprimes
up until x = 1015
, enumerating 1,801,533 pseudoprimes. This webpage is an effort to verify his work, and to extend it to x = 264-1
= 1.84 · 1019
. Such a list could be used for instance to construct fast reliable 64-bit primality test a-la Jaeschke
Many CPU years have been spent on the computating facilities of the University of Groningen
. The search ended in 2009 already, the resulting 264 list
soon found its way to the web. Unfortunately, Galway and myself never found the time nor energy to properly finalize the project in the form of an article...
However, more and more results have become relying on it, which calls for a better-late-than-never update of this webpage to disclose the algorithms and facilitate double-checking and such.
As of February 2013 most notes are available here so anyone can check them. This means I consider the project finished. Any comments
are welcome though!
The pseudoprimes are divided into two categories:
- category S: n is n1/2-smooth, i.e. all primes p which divide n satisfy p ≤ n1/2.
- category E: n is divisible by a prime q greater than n1/2.
A pseudoprime n is either in category S or in E.
Special attention is given to non-squarefree pseudoprimes
, because some of these are missed by the category S search algorithm.
The article of William Galway inspired me to start this project in the first place. Jaap Top
assisted with some algebraic details. All calculations were performed on machines from the University of Groningen
, with help from Arnold Meijster
. David Cleaver and Jeff Gilchrist
have performed quite a lot of double-checking effort. Specialized assembly code from Geoffrey Reynolds took many years off the total required computation time.