Fast tabulation of challenge pseudoprimes

DOI10.2140/OBS.2019.2.411MaRDI QIDQ6165878zbMATH OpenFDO

Authors Andrew Shallue, Jonathan Webster

Publication date 2 August 2023

Published in Open Book Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.08697

zbMATH Keywords

pseudoprimes

Mathematics Subject Classification ID

Primes (11A41) Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms (68W40)

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

Recommendations

• Tabulating Pseudoprimes and Tabulating Liars
• scientific article; zbMATH DE number 1643946
• Finding strong pseudoprimes to several bases. II
• Finding strong pseudoprimes to several bases
• Tabulating Absolute Lucas Pseudoprimes

Cites work

• A search for Wieferich and Wilson primes
• Algorithmic Number Theory
• Artin's conjecture for primitive roots
• Frobenius pseudoprimes
• scientific article; zbMATH DE number 1643946 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 2077510 (Why is no real title available?)
• Lucas Pseudoprimes
• On Numbers Analogous to the Carmichael Numbers
• On Strong Pseudoprimes to Several Bases
• Some Remarks on Artin's Conjecture
• Strong pseudoprimes to the first eight prime bases
• Strong pseudoprimes to twelve prime bases
• The Pseudoprimes to 25 ⋅10 9

Cited in

(4)

• Tabulating Carmichael numbers \(n=Pqr\) with small \(P\)
• Tabulating Pseudoprimes and Tabulating Liars
• scientific article; zbMATH DE number 7646865 (Why is no real title available?)
• Tabulating Absolute Lucas Pseudoprimes

This page was built for publication: Fast tabulation of challenge pseudoprimes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165878)