Strengthening the Baillie-PSW primality test

DOI10.1090/MCOM/3616MaRDI QIDQ4992237zbMATH OpenOpenAlexFDO

Authors Robert Baillie, Andrew Fiori, Samuel S. jun. Wagstaff

Publication date 7 June 2021

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

Lucas sequencesprimality test

Mathematics Subject Classification ID

Factorization; primality (11A51) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Primality (11Y11)

Abstract: The Baillie-PSW primality test combines Fermat and Lucas probable prime tests. It reports that a number is either composite or probably prime. No odd composite integer has been reported to pass this combination of primality tests if the parameters are chosen in an appropriate way. Here, we describe a significant strengthening of this test that comes at almost no additional computational cost. This is achieved by including in the test what we call Lucas-V pseudoprimes, of which there are only five less than $10^{15}$.

Recommendations

• scientific article; zbMATH DE number 1222545
• Lucas pseudoprimes of special types
• scientific article; zbMATH DE number 1164034
• scientific article; zbMATH DE number 1448712
• The Rabin-Monier theorem for Lucas pseudoprimes
• scientific article; zbMATH DE number 579184
• scientific article; zbMATH DE number 1995935
• A new primality test for natural integers
• Primality tests, linear recurrent sequences and the Pell equation
• scientific article; zbMATH DE number 3946211

Cites work

• A new lower bound for the pseudoprime counting function
• A probable prime test with high confidence
• Average liar count for degree-2 Frobenius pseudoprimes
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Frobenius pseudoprimes
• scientific article; zbMATH DE number 3124066 (Why is no real title available?)
• scientific article; zbMATH DE number 5010876 (Why is no real title available?)
• scientific article; zbMATH DE number 3666875 (Why is no real title available?)
• scientific article; zbMATH DE number 1131675 (Why is no real title available?)
• scientific article; zbMATH DE number 1467844 (Why is no real title available?)
• scientific article; zbMATH DE number 799757 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• Infinitely many Carmichael numbers in arithmetic progressions
• Lucas Pseudoprimes
• New Primality Criteria and Factorizations of 2 m ± 1
• On Numbers Analogous to the Carmichael Numbers
• Probabilistic algorithm for testing primality
• Strengthening the Baillie-PSW primality test
• The Carmichael Numbers up to 10 15
• The Pseudoprimes to 25 ⋅10 9
• The Rabin-Monier theorem for Lucas pseudoprimes
• There are infinitely many Carmichael numbers

Cited in

(14)

• An intelligent choice of witnesses in the Miller-Rabin primality test. Reinforcement learning approach
• A one-parameter quadratic-base version of the Baillie-PSW probable prime test
• scientific article; zbMATH DE number 1222361 (Why is no real title available?)
• scientific article; zbMATH DE number 1995935 (Why is no real title available?)
• scientific article; zbMATH DE number 1424174 (Why is no real title available?)
• Strengthening the Baillie-PSW primality test
• scientific article; zbMATH DE number 7626419 (Why is no real title available?)
• On elliptic Carmichael numbers in arithmetic progressions
• Bad witnesses for a composite number
• On the Baillie PSW conjecture
• On Lucas and Frobenius pseudoprimes
• Solutions of the Jin-Schmidt equation in Lucas numbers
• Novel performant primality test on a Pell's cubic
• Cyclotomic primes

This page was built for publication: Strengthening the Baillie-PSW primality test

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