First-hit analysis of algorithms for computing quadratic irregularity
HTML articles powered by AMS MathViewer
- by Joshua Holden PDF
- Math. Comp. 73 (2004), 939-948 Request permission
Abstract:
The author has previously extended the theory of regular and irregular primes to the setting of arbitrary totally real number fields. It has been conjectured that the Bernoulli numbers, or alternatively the values of the Riemann zeta function at odd negative integers, are uniformly distributed modulo $p$ for every $p$. This is the basis of a well-known heuristic, given by Siegel, estimating the frequency of irregular primes. So far, analyses have shown that if $\mathbf {Q}(\sqrt {D})$ is a real quadratic field, then the values of the zeta function $\zeta _{D}(1-2m)=\zeta _{\mathbf {Q}(\sqrt {D})}(1-2m)$ at negative odd integers are also distributed as expected modulo $p$ for any $p$. We use this heuristic to predict the computational time required to find quadratic analogues of irregular primes with a given order of magnitude. We also discuss alternative ways of collecting large amounts of data to test the heuristic.References
- Eric Bach, The complexity of number-theoretic constants, Inform. Process. Lett. 62 (1997), no. 3, 145–152. MR 1453698, DOI 10.1016/S0020-0190(97)00051-3
- C. Batut, K. Belabas, D. Bernardi, H. Cohen, and M. Olivier, User’s guide to PARI-GP, Laboratoire A2X, Université Bordeaux I, version 2.0.9 ed., May 13, 1998, http://www.parigp-home.de, ftp://megrez.math.u-bordeaux.fr.
- Ingrid Biehl, Johannes Buchmann, Safuat Hamdy, and Andreas Meyer, A signature scheme based on the intractability of extracting roots, Tech. Report Technical Report No. TI-1/00, Darmstadt University of Technology, 2000, http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/amy/Welcome.html.
- Johannes Buchmann and Volker Kessler, Computing a reduced lattice basis from a generating system, http://www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/reports/, 1992.
- Burton S. Kaliski Jr. (ed.), Advances in cryptology—CRYPTO ’97, Lecture Notes in Computer Science, vol. 1294, Springer-Verlag, Berlin, 1997. MR 1630391, DOI 10.1007/BFb0052223
- Johannes Buchmann and Oliver van Sprang, On short representations of orders and number fields, http://www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/reports/, 1992.
- J. P. Buhler, R. E. Crandall, and R. W. Sompolski, Irregular primes to one million, Math. Comp. 59 (1992), no. 200, 717–722. MR 1134717, DOI 10.1090/S0025-5718-1992-1134717-4
- J. P. Buhler, R. E. Crandall, and R. W. Sompolski, Irregular primes to one million, Math. Comp. 59 (1992), no. 200, 717–722. MR 1134717, DOI 10.1090/S0025-5718-1992-1134717-4
- 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
- Sandra Fillebrown, Faster computation of Bernoulli numbers, J. Algorithms 13 (1992), no. 3, 431–445. MR 1176671, DOI 10.1016/0196-6774(92)90048-H
- Tobias Hahn, Andreas Meyer, Stefan Neis, and Thomas Pfahler, Implementing cryptographic protocols based on algebraic number fields, Tech. Report Technical Report No. TI-24/99, Darmstadt University of Technology, 1999, http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/amy/Welcome.html.
- Joshua Holden, Irregularity of prime numbers over real quadratic fields, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 454–462. MR 1726093, DOI 10.1007/BFb0054884
- Joshua Brandon Holden, On the Fontaine-Mazur conjecture for number fields and an analogue for function fields, J. Number Theory 81 (2000), no. 1, 16–47. MR 1743506, DOI 10.1006/jnth.1999.2434
- Joshua Holden, Comparison of algorithms to calculate quadratic irregularity of prime numbers, Math. Comp. 71 (2002), no. 238, 863–871. MR 1885634, DOI 10.1090/S0025-5718-01-01341-2
- Wells Johnson, Irregular primes and cyclotomic invariants, Math. Comp. 29 (1975), 113–120. MR 376606, DOI 10.1090/S0025-5718-1975-0376606-9
- Walter F. Freiberger and William Prager (eds.), Applications of digital computers, Ginn and Company, Boston, Mass., 1963. MR 0152156
- Douglas C. Montgomery and George C. Runger, Applied statistics and probability for engineers, second ed., John Wiley & Sons, Inc., 1999.
- Carl Ludwig Siegel, Zu zwei Bemerkungen Kummers, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1964 (1964), 51–57 (German). MR 163899
- Samuel S. Wagstaff Jr., The irregular primes to $125000$, Math. Comp. 32 (1978), no. 142, 583–591. MR 491465, DOI 10.1090/S0025-5718-1978-0491465-4
- Lawrence C. Washington, Introduction to cyclotomic fields, 2nd ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997. MR 1421575, DOI 10.1007/978-1-4612-1934-7
- K. Wooldridge, Some results in arithmetical functions similar to Euler’s phi-function, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1975.
Additional Information
- Joshua Holden
- Affiliation: Department of Mathematics, Duke University, Durham, North Carolina 27708
- Address at time of publication: Department of Mathematics, Rose-Hulman Institute of Technology, Terre Haute, Indiana 47803
- Email: holden@rose-hulman.edu
- Received by editor(s): November 21, 2000
- Received by editor(s) in revised form: September 16, 2002
- Published electronically: July 28, 2003
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 73 (2004), 939-948
- MSC (2000): Primary 11Y40, 11Y60, 11Y16, 11R42; Secondary 11B68, 11R29, 94A60, 11R18
- DOI: https://doi.org/10.1090/S0025-5718-03-01593-X
- MathSciNet review: 2031416