Pseudoprimes

main page    database    statistics    verification   

Introduction

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.

Project status

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!

Search strategy

The pseudoprimes are divided into two categories: 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.

Acknowledgements

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.