Counting composites with two strong liars

DOI10.1090/MCOM/2949MaRDI QIDQ5501162zbMATH OpenOpenAlexFDO

Authors Eric Bach, Andrew Shallue

Publication date 13 August 2015

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

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

Mathematics Subject Classification ID

Primality (11Y11)

Abstract: The strong probable primality test is an important practical tool for discovering prime numbers. Its effectiveness derives from the following fact: for any odd composite number $n$, if a base $a$ is chosen at random, the algorithm is unlikely to claim that $n$ is prime. If this does happen we call $a$ a liar. In 1986, ErdH{o}s and Pomerance computed the normal and average number of liars, over all $nleqx$. We continue this theme and use a variety of techniques to count $nleqx$ with exactly two strong liars, those being the $n$ for which the strong test is maximally effective. We evaluate this count asymptotically and give an improved algorithm to determine it exactly. We also provide asymptotic counts for the restricted case in which $n$ has two prime factors, and for the $n$ with exactly two Euler liars.

Recommendations

• scientific article; zbMATH DE number 846096
• Tabulating Pseudoprimes and Tabulating Liars
• Further investigations with the strong probable prime test
• Finding strong pseudoprimes to several bases
• Average Case Error Estimates for the Strong Probable Prime Test

Cites work

• scientific article; zbMATH DE number 1614278 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3512236 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 3063029 (Why is no real title available?)
• scientific article; zbMATH DE number 3081798 (Why is no real title available?)
• A Heuristic Asymptotic Formula Concerning the Distribution of Prime Numbers
• A Simple Proof of a Theorem of Landau
• Algorithmic Number Theory
• Average Case Error Estimates for the Strong Probable Prime Test
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Faster integer multiplication
• On the Number of False Witnesses for a Composite Number
• On the normal number of prime factors of \(\phi(n)\)
• The large sieve
• Two contradictory conjectures concerning Carmichael numbers
• Zur additiven Zahlentheorie. II

Cited in

(2)

• scientific article; zbMATH DE number 846096 (Why is no real title available?)
• Average liar count for degree-2 Frobenius pseudoprimes

This page was built for publication: Counting composites with two strong liars

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