Counting composites with two strong liars

Bach, Eric; Shallue, Andrew

doi:10.1090/mcom/2949

Counting composites with two strong liars
HTML articles powered by AMS MathViewer

by Eric Bach and Andrew Shallue PDF

Math. Comp. 84 (2015), 3069-3089 Request permission

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, Erdős and Pomerance computed the normal and average number of liars, over all $n \leq x$. We continue this theme and use a variety of techniques to count $n \leq 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.

References

Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 148632, DOI 10.1090/S0025-5718-1962-0148632-7
Ivan Damgård, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), no. 203, 177–194. MR 1189518, DOI 10.1090/S0025-5718-1993-1189518-9
P. Erdös, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), 75–78. MR 29406
Paul Erdős and Carl Pomerance, On the normal number of prime factors of $\phi (n)$, Rocky Mountain J. Math. 15 (1985), no. 2, 343–352. Number theory (Winnipeg, Man., 1983). MR 823246, DOI 10.1216/RMJ-1985-15-2-343
Paul Erdős and Carl Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), no. 173, 259–279. MR 815848, DOI 10.1090/S0025-5718-1986-0815848-X
Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883–908. MR 1885636, DOI 10.1090/S0025-5718-01-01355-2
George Greaves, Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 43, Springer-Verlag, Berlin, 2001. MR 1836967, DOI 10.1007/978-3-662-04658-6
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
C. Hooley, Applications of sieve methods to the theory of numbers, Cambridge Tracts in Mathematics, No. 70, Cambridge University Press, Cambridge-New York-Melbourne, 1976. MR 0404173
E. Landau, Sur quelques problèmes relatifs à la distribution des nombres premiers, Bull. Soc. Math. France 28 (1900), 25–38 (French). MR 1504359
Edmund Landau, Handbuch der Lehre von der Verteilung der Primzahlen. 2 Bände, Chelsea Publishing Co., New York, 1953 (German). 2d ed; With an appendix by Paul T. Bateman. MR 0068565
Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, DOI 10.1016/0304-3975(80)90007-9
H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134. MR 374060, DOI 10.1112/S0025579300004708
Damien Stehlé and Paul Zimmermann, A binary recursive gcd algorithm, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 411–425. MR 2138011, DOI 10.1007/978-3-540-24847-7_{3}1
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
Arnold Walfisz, Zur additiven Zahlentheorie. II, Math. Z. 40 (1936), no. 1, 592–607 (German). MR 1545584, DOI 10.1007/BF01218882
E. M. Wright, A simple proof of a theorem of Landau, Proc. Edinburgh Math. Soc. (2) 9 (1954), 87–90. MR 65579, DOI 10.1017/S0013091500021349