Explicit bounds for primality testing and related problems

Bach, Eric

doi:10.1090/S0025-5718-1990-1023756-8

Explicit bounds for primality testing and related problems

Author: Eric Bach
Journal: Math. Comp. 55 (1990), 355-380
MSC: Primary 11R44; Secondary 11Y11, 11Y40
DOI: https://doi.org/10.1090/S0025-5718-1990-1023756-8
MathSciNet review: 1023756
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Many number-theoretic algorithms rely on a result of Ankeny, which states that if the Extended Riemann Hypothesis (ERH) is true, any nontrivial multiplicative subgroup of the integers modulo m omits a number that is $O({\log ^2}m)$ . This has been generalized by Lagarias, Montgomery, and Odlyzko to give a similar bound for the least prime ideal that does not split completely in an abelian extension of number fields. This paper gives a different proof of this theorem, in which explicit constants are supplied. The bounds imply that if the ERH holds, a composite number m has a witness for its compositeness (in the sense of Miller or Solovay-Strassen) that is at most $2{\log ^2}m$ .

[1] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1965.
[2] Leonard Adleman, Kenneth Manders, and Gary Miller, On taking roots in finite fields, 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977) IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 175–178. MR 0502224
[3] Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, https://doi.org/10.2307/2006975
[4] N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 0045159, https://doi.org/10.2307/1969420
[5] Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
[6] Eric Bach and Jeffrey Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), no. 185, 201–219. MR 947467, https://doi.org/10.1090/S0025-5718-1989-0947467-1
[7] Richard P. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), no. 148, 1361–1372. MR 537983, https://doi.org/10.1090/S0025-5718-1979-0537983-2
[8] J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1986. Reprint of the 1967 original. MR 911121
[9] Harvey Cohn, Advanced number theory, Dover Publications, Inc., New York, 1980. Reprint of A second course in number theory, 1962; Dover Books on Advanced Mathematics. MR 594936
[10] W. J. Cody and Henry C. Thacher Jr., Chebyshev approximations for the exponential integral 𝐸𝑖(𝑥), Math. Comp. 23 (1969), 289–303. MR 0242349, https://doi.org/10.1090/S0025-5718-1969-0242349-2
[11] H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, https://doi.org/10.1090/S0025-5718-1984-0726006-X
[12] Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931
[13] D. Davies and C. B. Haselgrove, The evaluation of Dirichlet 𝐿-functions, Proc. Roy. Soc. Ser. A 264 (1961), 122–132. MR 0136052
[14] D. Davies, An approximate functional equation for Dirichlet 𝐿-functions, Proc. Roy. Soc. Ser. A 284 (1965), 224–236. MR 0173352
[15] H. M. Edwards, Riemann's zeta function, Academic Press, New York, 1974.
[16] Richard P. Feynman, Robert B. Leighton, and Matthew Sands, The Feynman lectures on physics. Vol. 2: Mainly electromagnetism and matter, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1964. MR 0213078
[17] Larry Joel Goldstein, Analytic number theory, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR 0498335
[18] S. Graham and R. J. Ringrose, Lower bounds for least quadratic non-residues, manuscript, 1988.
[19] Helmut Hasse, Bericht über neuere Untersuchungen und Probleme aus der Theorie der algebraischen Zahlkörper. Teil I: Klassenkörpertheorie. Teil Ia: Beweise zu Teil I. Teil II: Reziprozitätsgesetz, Dritte Auflage, Physica-Verlag, Würzburg-Vienna, 1970 (German). MR 0266893
[20] M. A. Huang, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM Symposium on Theory of Computing, 1985, pp. 121-130.
[21] A. E. Ingham, The distribution of prime numbers, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1990. Reprint of the 1932 original; With a foreword by R. C. Vaughan. MR 1074573
[22] J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: 𝐿-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
[23] J. C. Lagarias and A. M. Odlyzko, On computing Artin 𝐿-functions in the critical strip, Math. Comp. 33 (1979), no. 147, 1081–1095. MR 528062, https://doi.org/10.1090/S0025-5718-1979-0528062-9
[24] J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223, https://doi.org/10.1007/BF01390234
[25] Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
[26] D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433–451. MR 0271006, https://doi.org/10.1090/S0025-5718-1970-0271006-X
[27] A. K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 443–454. MR 976527
[28] J. van de Lune, H. J. J. te Riele, and D. T. Winter, On the zeros of the Riemann zeta function in the critical strip. IV, Math. Comp. 46 (1986), no. 174, 667–681. MR 829637, https://doi.org/10.1090/S0025-5718-1986-0829637-3
[29] Peter McCullagh, A rapidly convergent series for computing 𝜓(𝑧) and its derivatives, Math. Comp. 36 (1981), no. 153, 247–248. MR 595057, https://doi.org/10.1090/S0025-5718-1981-0595057-8
[30] Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR 0480295, https://doi.org/10.1016/S0022-0000(76)80043-8
[31] Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR 0337847
[32] A. M. Odlyzko, Lower bounds for discriminants of number fields, Acta Arith. 29 (1976), no. 3, 275–297. MR 0401704, https://doi.org/10.4064/aa-29-3-275-297
[33] A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), no. 177, 273–308. MR 866115, https://doi.org/10.1090/S0025-5718-1987-0866115-0
[34] J. Oesterlé, Versions effectives du théorème de Chebotarev sous l'hypothèse de Riemann généralisée, Soc. Math. France Astérisque 61 (1979), 165-167.
[35] Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to 25⋅10⁹, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, https://doi.org/10.1090/S0025-5718-1980-0572872-7
[36] Guy Robin, Estimation de la fonction de Tchebychef 𝜃 sur le 𝑘-ième nombre premier et grandes valeurs de la fonction 𝜔(𝑛) nombre de diviseurs premiers de 𝑛, Acta Arith. 42 (1983), no. 4, 367–389 (French). MR 736719, https://doi.org/10.4064/aa-42-4-367-389
[37] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 0137689
[38] Lajos Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391–400. MR 955147, https://doi.org/10.1016/0196-6774(88)90029-6
[39] C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, https://doi.org/10.1090/S0025-5718-1984-0744939-5
[40] Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, https://doi.org/10.1090/S0025-5718-1987-0878705-X
[41] Daniel Shanks, Systematic examination of Littlewood’s bounds on 𝐿(1,𝜒), Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972) Amer. Math. Soc., Providence, R.I., 1973, pp. 267–283. MR 0337827
[42] Robert Spira, Calculation of Dirichlet 𝐿-functions, Math. Comp. 23 (1969), 489–497. MR 0247742, https://doi.org/10.1090/S0025-5718-1969-0247742-X
[43] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 0429721, https://doi.org/10.1137/0206006
[44] H. M. Stark, Some effective cases of the Brauer-Siegel theorem, Invent. Math. 23 (1974), 135–152. MR 0342472, https://doi.org/10.1007/BF01405166
[45] J. Vélu, Tests for primality under the Riemann hypothesis, SIGACT News 10 (1978), 58-59.
[46] Alwin Walther, Anschauliches zur Riemannschen Zetafunktion, Acta Math. 48 (1926), no. 3-4, 393–400 (German). MR 1555234, https://doi.org/10.1007/BF02565343
[47] Peter J. Weinberger, On small zeros of Dirichlet 𝐿-functions, Math. Comp. 29 (1975), 319–328. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR 0376564, https://doi.org/10.1090/S0025-5718-1975-0376564-7
[48] A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society Mathematical Tables, Vol. 9, Published for the Royal Society at the Cambridge University Press, London, 1968. MR 0246488