Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Counting composites with two strong liars


Authors: Eric Bach and Andrew Shallue
Journal: Math. Comp. 84 (2015), 3069-3089
MSC (2010): Primary 11Y11
DOI: https://doi.org/10.1090/mcom/2949
Published electronically: April 1, 2015
MathSciNet review: 3378863
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363-367. MR 0148632 (26 #6139)
  • [2] 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 (94b:11124), https://doi.org/10.2307/2152945
  • [3] P. Erdös, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), 75-78. MR 0029406 (10,594d)
  • [4] 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 (87e:11112), https://doi.org/10.1216/RMJ-1985-15-2-343
  • [5] 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 (87i:11183), https://doi.org/10.2307/2008231
  • [6] Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979-1005. MR 2538847 (2011b:68296), https://doi.org/10.1137/070711761
  • [7] Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883-908. MR 1885636 (2003d:11148), https://doi.org/10.1090/S0025-5718-01-01355-2
  • [8] 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 (2002i:11092)
  • [9] 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 (81i:10002)
  • [10] C. Hooley, Applications of Sieve Methods to the Theory of Numbers, Cambridge University Press, Cambridge, New York, Melbourne, 1976. Cambridge Tracts in Mathematics, No. 70. MR 0404173 (53 #7976)
  • [11] E. Landau, Sur quelques problèmes relatifs à la distribution des nombres premiers, Bull. Soc. Math. France 28 (1900), 25-38 (French). MR 1504359
  • [12] 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 (16,904d)
  • [13] Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97-108. MR 582244 (82a:68078), https://doi.org/10.1016/0304-3975(80)90007-9
  • [14] H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119-134. MR 0374060 (51 #10260)
  • [15] 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 (2006e:11194), https://doi.org/10.1007/978-3-540-24847-7_31
  • [16] Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757 (2004g:68202)
  • [17] Arnold Walfisz, Zur additiven Zahlentheorie. II, Math. Z. 40 (1936), no. 1, 592-607 (German). MR 1545584, https://doi.org/10.1007/BF01218882
  • [18] E. M. Wright, A simple proof of a theorem of Landau, Proc. Edinburgh Math. Soc. (2) 9 (1954), 87-90. MR 0065579 (16,448e)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y11

Retrieve articles in all journals with MSC (2010): 11Y11


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
Email: ashallue@iwu.edu

DOI: https://doi.org/10.1090/mcom/2949
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society