Thirteenth Algorithmic Number Theory Symposium ANTS-XIII University of Wisconsin, Madison July 16 – 20, 2018 Thirteenth Algorithmic Number Theory Symposium (ANTS-XIII) July 16 – 20, 2018

Fast tabulation of challenge pseudoprimes

Jonathan Webster and Andrew Shallue

Abstract: We provide a new algorithm for tabulating composite numbers which are pseudoprimes to both a Fermat test and a Lucas test. Our algorithm is optimized for parameter choices that minimize the occurrence of pseudoprimes, and for pseudoprimes with a fixed number of prime factors. Using this, we have confirmed that there are no PSW challenge pseudoprimes with two or three prime factors up to 2⁸⁰. In the case where one is tabulating challenge pseudoprimes with a fixed number of prime factors, we prove our algorithm gives an unconditional asymptotic improvement over previous methods.

Published Paper
Talk Slides