Explicit bounds for primality testing and related problems
HTML articles powered by AMS MathViewer
- by Eric Bach PDF
- Math. Comp. 55 (1990), 355-380 Request permission
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$.References
-
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 10.2307/2006975
- N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI 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 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 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 Books on Advanced Mathematics, Dover Publications, Inc., New York, 1980. Reprint of A second course in number theory, 1962. MR 594936
- W. J. Cody and Henry C. Thacher Jr., Chebyshev approximations for the exponential integral $\textrm {Ei}(x)$, Math. Comp. 23 (1969), 289–303. MR 242349, DOI 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 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 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 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 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 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 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 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 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 10.1016/S0022-0000(76)80043-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 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 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 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 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 10.1016/0196-6774(88)90029-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 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 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 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 10.1137/0206006
- H. M. Stark, Some effective cases of the Brauer-Siegel theorem, Invent. Math. 23 (1974), 135–152. MR 342472, DOI 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 10.1007/BF02565343
- Peter J. Weinberger, On small zeros of Dirichlet $L$-functions, Math. Comp. 29 (1975), 319–328. MR 376564, DOI 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
Additional Information
- © Copyright 1990 American Mathematical Society
- 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