**
**

# Pseudoprimes

**main page**
database
statistics
verification
### Introduction

In 2002,

William Galway compiled a complete

list of base-2

Fermat pseudoprimes up until x = 10

^{15}, enumerating 1,801,533 pseudoprimes. This webpage is an effort to verify his work, and to extend it to

**x = 2**^{64}-1 = 1.84 · 10

^{19}. 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

2^{64} 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:

- category S: n is n
^{1/2}-smooth, i.e. all primes p which divide n satisfy p ≤ n^{1/2}.
- category E: n is divisible by a prime q greater than n
^{1/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.

### 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.