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

Handbook of mathematical functions

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

Riemann’s zeta function

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

Lower bounds for least quadratic non-residues

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

Riemann hypothesis and finding roots over finite fields

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

Versions effectives du théorème de Chebotarev sous l’hypothèse de Riemann généralisée

61

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

Tests for primality under the Riemann hypothesis

10

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