2013/08/05 by Eric Bach, Bach, Eric, Andrew Shallue +1
Computer Science · Mathematics · #11Y11 #Analytic Number Theory Research #Cryptography and Residue Arithmetic #FOS: Mathematics #History and Theory of Mathematics #Number Theory (math.NT) #math.NT #msc:11Y11
paper · pdf · doi:10.48550/arxiv.1308.0880
arxiv created 2013/08/05 · openalex publication_date 2013/08/05 · arxiv updated 2013/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, Erdős and Pomerance computed the normal and average number of liars, over all n ≤ x. We continue this theme and use a variety of techniques to count n ≤ x 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.