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 Free Access

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$.

M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1965.

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
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, DOI https://doi.org/10.2307/2006975
N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI https://doi.org/10.2307/1969420
Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
Eric Bach and Jeffrey Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), no. 185, 201–219. MR 947467, DOI https://doi.org/10.1090/S0025-5718-1989-0947467-1
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, DOI https://doi.org/10.1090/S0025-5718-1979-0537983-2
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
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
W. J. Cody and Henry C. Thacher Jr., Chebyshev approximations for the exponential integral ${\rm Ei}(x)$, Math. Comp. 23 (1969), 289–303. MR 242349, DOI https://doi.org/10.1090/S0025-5718-1969-0242349-2
H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI https://doi.org/10.1090/S0025-5718-1984-0726006-X
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
D. Davies and C. B. Haselgrove, The evaluation of Dirichlet $L$-functions, Proc. Roy. Soc. London Ser. A 264 (1961), 122–132. MR 136052, DOI https://doi.org/10.1098/rspa.1961.0187
D. Davies, An approximate functional equation for Dirichlet $L$-functions, Proc. Roy. Soc. London Ser. A 284 (1965), 224–236. MR 173352, DOI https://doi.org/10.1098/rspa.1965.0060

H. M. Edwards, Riemann’s zeta function, Academic Press, New York, 1974.

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
Larry Joel Goldstein, Analytic number theory, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR 0498335

S. Graham and R. J. Ringrose, Lower bounds for least quadratic non-residues, manuscript, 1988.

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, Physica-Verlag, Würzburg-Vienna, 1970 (German). Dritte Auflage. MR 0266893

M. A. Huang, Riemann hypothesis and finding roots over finite fields, Proc. 17th ACM Symposium on Theory of Computing, 1985, pp. 121-130.

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
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
J. C. Lagarias and A. M. Odlyzko, On computing Artin $L$-functions in the critical strip, Math. Comp. 33 (1979), no. 147, 1081–1095. MR 528062, DOI https://doi.org/10.1090/S0025-5718-1979-0528062-9
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, DOI https://doi.org/10.1007/BF01390234
Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433–451. MR 271006, DOI https://doi.org/10.1090/S0025-5718-1970-0271006-X
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
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, DOI https://doi.org/10.1090/S0025-5718-1986-0829637-3
Peter McCullagh, A rapidly convergent series for computing $\psi (z)$ and its derivatives, Math. Comp. 36 (1981), no. 153, 247–248. MR 595057, DOI https://doi.org/10.1090/S0025-5718-1981-0595057-8
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI https://doi.org/10.1016/S0022-0000%2876%2980043-8
Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. MR 0337847
A. M. Odlyzko, Lower bounds for discriminants of number fields, Acta Arith. 29 (1976), no. 3, 275–297. MR 401704, DOI https://doi.org/10.4064/aa-29-3-275-297
A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), no. 177, 273–308. MR 866115, DOI https://doi.org/10.1090/S0025-5718-1987-0866115-0

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.

Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI https://doi.org/10.1090/S0025-5718-1980-0572872-7
Guy Robin, Estimation de la fonction de Tchebychef $\theta $ sur le $k$-ième nombre premier et grandes valeurs de la fonction $\omega (n)$ nombre de diviseurs premiers de $n$, Acta Arith. 42 (1983), no. 4, 367–389 (French). MR 736719, DOI https://doi.org/10.4064/aa-42-4-367-389
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Lajos Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391–400. MR 955147, DOI https://doi.org/10.1016/0196-6774%2888%2990029-6
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, DOI https://doi.org/10.1090/S0025-5718-1984-0744939-5
Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, DOI https://doi.org/10.1090/S0025-5718-1987-0878705-X
Daniel Shanks, Systematic examination of Littlewood’s bounds on $L(1,\,\chi )$, 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
Robert Spira, Calculation of Dirichlet $L$-functions, Math. Comp. 23 (1969), 489–497. MR 247742, DOI https://doi.org/10.1090/S0025-5718-1969-0247742-X
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI https://doi.org/10.1137/0206006
H. M. Stark, Some effective cases of the Brauer-Siegel theorem, Invent. Math. 23 (1974), 135–152. MR 342472, DOI https://doi.org/10.1007/BF01405166

J. Vélu, Tests for primality under the Riemann hypothesis, SIGACT News 10 (1978), 58-59.

Alwin Walther, Anschauliches zur Riemannschen Zetafunktion, Acta Math. 48 (1926), no. 3-4, 393–400 (German). MR 1555234, DOI https://doi.org/10.1007/BF02565343
Peter J. Weinberger, On small zeros of Dirichlet $L$-functions, Math. Comp. 29 (1975), 319–328. MR 376564, DOI https://doi.org/10.1090/S0025-5718-1975-0376564-7
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