Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
2: ANTS XIII
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
 
Other MSP Publications
Fast tabulation of challenge pseudoprimes

Andrew Shallue and Jonathan Webster

Vol. 2 (2019), No. 1, 411–423
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 280 . 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.

Keywords
pseudoprimes
Mathematical Subject Classification 2010
Primary: 11Y11, 11Y16
Secondary: 11A41, 68W40
Milestones
Received: 2 March 2018
Revised: 18 June 2018
Accepted: 17 September 2018
Published: 13 February 2019
Authors
Andrew Shallue
Department of Mathematics
Illinois Wesleyan University
Bloomington, IL
United States
Jonathan Webster
Department of Mathematics, Statistics & Actuarial Science
Butler University
Indianapolis, IN
United States