×

Explicit bounds for primality testing and related problems. (English) Zbl 0701.11075

In his very readable book [“Analytic methods in the analysis and design of number-theoretic algorithms” (MIT Press, Cambridge 1985; Zbl 0572.10001)] the author found a constant for Ankeny’s Theorem that if G is a proper subgroup of \(({\mathbb{Z}}/m{\mathbb{Z}})^*\), then the smallest integer w not in G must exceed 2 log\({}^ 2m\). Here he extends his methods to algebraic number fields according to J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko [Invent. Math. 54, 271-296 (1979; Zbl 0401.12014)].
Here, analogously, the least prime ideal which does not split in E/K (of absolute discriminant \(\Delta\), and conductor \({\mathfrak f})\) has norm less than 3 log\({}^ 2(\Delta^ 2N{\mathfrak f})\). If we insist that w be relatively prime to m, then the multiplier “2” should be replaced by “3”. Also if the ideal is to be relatively prime to \({\mathfrak f}\) then the “3” is replaced by a “12”, while if the ideal is to also completely split, the constant becomes “18”. All constants may be replaced by \(1+o(1),\) and tables support this latter result numerically.
Reviewer: H.Cohn

MSC:

11Y11 Primality
11R29 Class numbers, class groups, discriminants
11M26 Nonreal zeros of \(\zeta (s)\) and \(L(s, \chi)\); Riemann and other hypotheses
11A15 Power residues, reciprocity
11R44 Distribution of prime ideals
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1965. · Zbl 0171.38503
[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.
[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. · Zbl 0526.10004 · doi:10.2307/2006975
[4] N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65 – 72. · Zbl 0046.04006 · doi: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. · Zbl 0572.10001
[6] Eric Bach and Jeffrey Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), no. 185, 201 – 219. · Zbl 0661.10008
[7] Richard P. Brent, On the zeros of the Riemann zeta function in the critical strip, Math. Comp. 33 (1979), no. 148, 1361 – 1372. · Zbl 0422.10031
[8] J. W. S. Cassels and A. Fröhlich , Algebraic number theory, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1986. Reprint of the 1967 original. · Zbl 0153.07403
[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. · Zbl 0208.31501
[10] W. J. Cody and Henry C. Thacher Jr., Chebyshev approximations for the exponential integral \?\?(\?), Math. Comp. 23 (1969), 289 – 303. · Zbl 0176.13902
[11] H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297 – 330. · Zbl 0578.10004
[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. · Zbl 0453.10002
[13] D. Davies and C. B. Haselgrove, The evaluation of Dirichlet \?-functions, Proc. Roy. Soc. Ser. A 264 (1961), 122 – 132. · Zbl 0109.03102
[14] D. Davies, An approximate functional equation for Dirichlet \?-functions, Proc. Roy. Soc. Ser. A 284 (1965), 224 – 236. · Zbl 0131.04601
[15] H. M. Edwards, Riemann’s zeta function, Academic Press, New York, 1974. · Zbl 0315.10035
[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.
[17] Larry Joel Goldstein, Analytic number theory, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. · Zbl 0226.12001
[18] S. Graham and R. J. Ringrose, Lower bounds for least quadratic non-residues, manuscript, 1988. · Zbl 0719.11006
[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). · JFM 56.0165.01
[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. · Zbl 0715.11045
[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. · Zbl 0362.12011
[23] J. C. Lagarias and A. M. Odlyzko, On computing Artin \?-functions in the critical strip, Math. Comp. 33 (1979), no. 147, 1081 – 1095. · Zbl 0409.12017
[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. · Zbl 0401.12014 · doi:10.1007/BF01390234
[25] Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. · Zbl 0211.38404
[26] D. H. Lehmer, Emma Lehmer, and Daniel Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), 433 – 451. · Zbl 0203.35301
[27] A. K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 443 – 454. · Zbl 0669.10012
[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. · Zbl 0585.10023
[29] Peter McCullagh, A rapidly convergent series for computing \?(\?) and its derivatives, Math. Comp. 36 (1981), no. 153, 247 – 248. · Zbl 0462.33003
[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). , https://doi.org/10.1016/S0022-0000(76)80043-8 Gary L. Miller, Riemann’s hypothesis and tests for primality, Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N.M., 1975), Assoc. Comput. Mach., New York, 1975, pp. 234 – 239. · Zbl 0349.68025
[31] Hugh L. Montgomery, Topics in multiplicative number theory, Lecture Notes in Mathematics, Vol. 227, Springer-Verlag, Berlin-New York, 1971. · Zbl 0216.03501
[32] A. M. Odlyzko, Lower bounds for discriminants of number fields, Acta Arith. 29 (1976), no. 3, 275 – 297. · Zbl 0286.12006
[33] A. M. Odlyzko, On the distribution of spacings between zeros of the zeta function, Math. Comp. 48 (1987), no. 177, 273 – 308. · Zbl 0615.10049
[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. · Zbl 0418.12005
[35] 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. · Zbl 0444.10007
[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). · Zbl 0475.10034
[37] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64 – 94. · Zbl 0122.05001
[38] Lajos Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391 – 400. · Zbl 0651.12013 · doi: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. · Zbl 0559.10004
[40] Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757 – 780. · Zbl 0619.10004
[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.
[42] Robert Spira, Calculation of Dirichlet \?-functions, Math. Comp. 23 (1969), 489 – 497. , https://doi.org/10.1090/S0025-5718-1969-0247742-X Robert Spira, Tables and programs for Dirichlet \?-series, Math. Comp. 23 (1969), no. 107, loose microfiche suppl. · Zbl 0182.07001 · doi:10.2307/2004376
[43] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84 – 85. · Zbl 0345.10002 · doi:10.1137/0206006
[44] H. M. Stark, Some effective cases of the Brauer-Siegel theorem, Invent. Math. 23 (1974), 135 – 152. · Zbl 0278.12005 · doi: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). · JFM 52.0337.01 · doi: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. · Zbl 0301.10035
[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. · Zbl 0175.32501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.