Placed on this website with authorisation from the American Mathematical Society and the authors. Original prints supplied by Samuel S. Wagstaff.
Revised: 2003-03-27
Carl Pomerance, J.L. Selfridge and Samuel S. Wagstaff, Jr.
The Pseudoprimes to 25.10^9
in Mathematics of Computation, Volume 35, Number 151, July 1980, pages 1003-1026.
Robert Baillie and Samuel S. Wagstaff, Jr.
Lucas Pseudoprimes
in Mathematics of Computation, Volume 35, Number 152, October 1980, pages 1391-1417.
These papers in particular describe very fast probable prime tests that have no known exception: a strong pseudoprime test to base 2 combined with either one of two refined instances of Lehmer's Lucas test.
A famous challenge on this combination of tests is stated in the first article.
The second article is of interest to implementors of ANSI X9.31 and ANSI X9.80, since these standards recommand (among other possibilities) the first of these two Lucas tests, and the paper gives a list of pseudoprimes.