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
Additional Information
- Eric Bach
- Affiliation: University of Wisconsin–Madison, 1210 W. Dayton St., Madison, Wisconsin 53706
- Email: bach@cs.wisc.edu
- Andrew Shallue
- Affiliation: Illinois Wesleyan University, 1312 Park St., Bloomington, Illinois 61701
- MR Author ID: 805175
- Email: ashallue@iwu.edu
- Received by editor(s): August 4, 2013
- Received by editor(s) in revised form: February 16, 2014
- Published electronically: April 1, 2015
- Additional Notes: This research supported by NSF: CCF-0635355 and ARO: W911NF9010439
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 3069-3089
- MSC (2010): Primary 11Y11
- DOI: https://doi.org/10.1090/mcom/2949
- MathSciNet review: 3378863