Counting composites with two strong liars

DOI10.1090/MCOM/2949zbMATH Open1330.11079arXiv1308.0880OpenAlexW2151646231MaRDI QIDQ5501162FDOQ5501162

Authors: Eric Bach, Andrew Shallue 

Publication date: 13 August 2015

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

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.

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

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

Mathematics Subject Classification ID

Primality (11Y11)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• 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)