Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Explicit bounds for primality testing and related problems

Author(s): Eric Bach.
Journal: Math. Comp. 55 (1990), 355-380.
MSC: Primary 11R44; Secondary 11Y11, 11Y40
MathSciNet review: 1023756
Retrieve article in: PDF
This article is available free of charge

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

References:

[1]: M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1965.
[2]: L. Adleman, K. Manders, and G. Miller, On taking roots in finite fields, Proc. 18th IEEE Symposium on Foundations of Computer Science, 1977, pp. 175-177. MR 0502224 (58:19339)
[3]: L. Adleman, C. Pomerance, and R. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), 173-206. MR 683806 (84e:10008)
[4]: N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65-72. MR 0045159 (13:538c)
[5]: E. Bach, Analytic methods in the analysis and design of number-theoretic algorithms, MIT Press, Cambridge, Mass., 1985. MR 807772 (87i:11185)
[6]: E. Bach and J. Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989). 201-219. MR 947467 (89k:11127)
[7]: R. P. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), 1361-1372. MR 537983 (80g:10033)
[8]: J. W. S. Cassels and A. Fröhlich, Algebraic number theory, Academic Press, London, 1986. MR 911121 (88h:11073)
[9]: H. Cohn, Advanced number theory, Dover, New York, 1980. MR 594936 (82b:12001)
[10]: W. J. Cody and H. C. Thacher, Jr., Chebyshev approximations for the exponential integral ${\text{Ei}}(x)$ , Math. Comp. 23 (1969), 289-303. MR 0242349 (39:3680)
[11]: H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), 287-330. MR 726006 (86g:11078)
[12]: H. Davenport, Multiplicative number theory, Springer, Berlin, 1980. MR 606931 (82m:10001)
[13]: D. Davies and C. B. Haselgrove, The evaluation of Dirichlet L-functions, Proc. Roy. Soc. London Ser. A 264 (1961), 122-132. MR 0136052 (24:B2091)
[14]: D. Davies, An approximate functional equation for Dirichlet L-functions, Proc. Roy. Soc. London Ser. A 284 (1965), 224-236. MR 0173352 (30:3565)
[15]: H. M. Edwards, Riemann's zeta function, Academic Press, New York, 1974.
[16]: R. P. Feynman, R. B. Leighton, and M. Sands, The Feynman lectures on physics, vol. 2, Addison-Wesley, Reading, Mass., 1964. MR 0213078 (35:3943)
[17]: L. J. Goldstein, Analytic number theory, Prentice-Hall, Englewood Cliffs, N. J., 1971. MR 0498335 (58:16471)
[18]: S. Graham and R. J. Ringrose, Lower bounds for least quadratic non-residues, manuscript, 1988.
[19]: H. Hasse, Bericht über neuere Untersuchungen und Probleme aus der Theorie der algebraischen Zahlkörper, 3rd ed., Physica-Verlag, Würzburg-Wien, 1970. MR 0266893 (42:1795)
[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 Univ. Press, Cambridge, 1932. MR 1074573 (91f:11064)
[22]: J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, in Algebraic Number Fields (A. Fröhlich, ed.), Academic Press, London, 1977. MR 0447191 (56:5506)
[23]: -, On computing Artin L-functions in the critical strip, Math. Comp. 33 (1979), 1081-1095. MR 528062 (80g:12010)
[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), 271-296. MR 553223 (81b:12013)
[25]: S. Lang, Algebraic number theory, Addison-Wesley, Reading, Mass., 1971. MR 0282947 (44:181)
[26]: D. H. Lehmer, E. Lehmer, and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433-451. MR 0271006 (42:5889)
[27]: A. K. Lenstra, Fast and rigorous factorization under the extended Riemann hypothesis, Indag. Math. 50 (1988), 443-454. MR 976527 (90a:11152)
[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), 667-681. MR 829637 (87e:11102)
[29]: P. McCullagh, A rapidly convergent series for computing $\psi (z)$ and its derivatives, Math. Comp. 36 (1981), 247-248. MR 595057 (81m:65028)
[30]: G. L. Miller, Riemann's hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), 300-317. MR 0480295 (58:470a)
[31]: H. L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Math., vol. 227, Springer, Berlin, 1971. MR 0337847 (49:2616)
[32]: A. M. Odlyzko, Lower bounds for discriminants of number fields, Acta Arith. 29 (1976), 275-297. MR 0401704 (53:5531)
[33]: -, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), 273-308. MR 866115 (88d:11082)
[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]: C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to $25 \cdot {10^9}$ , Math. Comp. 25 (1980), 1003-1026. MR 572872 (82g:10030)
[36]: G. 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), 367-389. MR 736719 (85j:11109)
[37]: J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 0137689 (25:1139)
[38]: L. Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), 391-400. MR 955147 (89k:11124)
[39]: C. P. Schnorr and H. W. Lenstra, Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), 289-311. MR 744939 (85d:11106)
[40]: M. Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), 757-780. MR 878705 (88d:11129)
[41]: D. Shanks, Systematic examination of Littlewood's bounds on $L(1,\chi )$ , Proc. Sympos. Pure Math., vol. 24, Amer. Math. Soc., Providence, R. I., 1973, pp. 294-311. MR 0337827 (49:2596)
[42]: R. Spira, Calculation of Dirichlet L-functions, Math. Comp. 23 (1969), 489-497. MR 0247742 (40:1004a)
[43]: R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), 84-85. MR 0429721 (55:2732)
[44]: H. M. Stark, Effective cases of the Brauer-Siegel theorem, Invent. Math. 23 (1974), 135-152. MR 0342472 (49:7218)
[45]: J. Vélu, Tests for primality under the Riemann hypothesis, SIGACT News 10 (1978), 58-59.
[46]: A. Walther, Anschauliches zur Riemannschen Zetafunktion, Acta Math. 48 (1926), 393-400. MR 1555234
[47]: P. J. Weinberger, On small zeros of Dirichlet L-functions, Math. Comp. 29 (1975), 319-328. MR 0376564 (51:12739)
[48]: A. E. Western and J. C. P. Miller, Tables of indices and primitive roots, Royal Society, Cambridge, 1968. MR 0246488 (39:7792)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|