Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
4: ANTS XIV
3: Hillman: Poincaré Duality
2: ANTS XIII
1: ANTS X
The Open Book Series
All Volumes
 
About the Series
Ethics Statement
Purchase Printed Copies
Author Index
 
MSP Books and Monographs
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