Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



First-hit analysis of algorithms for computing quadratic irregularity

Author: Joshua Holden
Journal: Math. Comp. 73 (2004), 939-948
MSC (2000): Primary 11Y40, 11Y60, 11Y16, 11R42; Secondary 11B68, 11R29, 94A60, 11R18
Published electronically: July 28, 2003
MathSciNet review: 2031416
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Eric Bach, The complexity of number-theoretic constants, Inform. Process. Lett. 62 (1997), 145-152. MR 98g:11148
  • 2. 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, <>, <>.
  • 3. 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, <>.
  • 4. Johannes Buchmann and Volker Kessler, Computing a reduced lattice basis from a generating system, <>, 1992.
  • 5. Johannes Buchmann and Sachar Paulus, A one way function based on ideal arithmetic in number fields, Advances in Cryptology--CRYPTO '97 (Burton S. Kaliski, Jr, ed.), Lecture Notes in Computer Science, vol. 1294, Springer-Verlag, 1997, pp. 385-394. MR 99a:94041
  • 6. Johannes Buchmann and Oliver van Sprang, On short representations of orders and number fields, <>, 1992.
  • 7. J. Buhler, R. Crandall, R. Ernvall, and T. Metsänkylä, Irregular primes and cyclotomic invariants up to four million, Math. Comp. 59 (1992), 717-722. MR 93a:11106
  • 8. J. P. Buhler, R. E. Crandall, and R. W. Sompolski, Irregular primes to one million, Math. Comp. 59 (1992), 717-722. MR 93a:11106
  • 9. J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Academic Press, 1986, Reprint of the 1967 original. MR 88h:11073
  • 10. Sandra Fillebrown, Faster computation of Bernoulli numbers, J. Algorithms 13 (1992), 431-445. MR 94d:68044
  • 11. 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, <>.
  • 12. Joshua Holden, Irregularity of prime numbers over real quadratic fields, Algorithmic Number Theory: Third International Symposium; Proceedings (J. P. Buhler, ed.), Springer Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, 1998, pp. 454-462. MR 2000m:11113
  • 13. -, On the Fontaine-Mazur Conjecture for number fields and an analogue for function fields, J. Number Theory 81 (2000), 16-47. MR 2001e:11111
  • 14. -, Comparison of algorithms to calculate quadratic irregularity of prime numbers, Math. Comp. 71 (2002), 863-871. MR 2003d:11183
  • 15. Wells Johnson, Irregular primes and cyclotomic invariants, Math. Comp. 29 (1975), 113-120. MR 51:12781
  • 16. D. H. Lehmer, Automation and pure mathematics, Applications of Digital Computers (Walter F. Freiberger and William Prager, eds.), Ginn and Company, Boston, 1963, pp. 219-231. MR 27:2136
  • 17. Douglas C. Montgomery and George C. Runger, Applied statistics and probability for engineers, second ed., John Wiley & Sons, Inc., 1999.
  • 18. Carl Ludwig Siegel, Zu zwei bemerkungen Kummers, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 6 (1964), 51-57. MR 29:1198
  • 19. Samuel S. Wagstaff, Jr., The irregular primes to 125000, Math. Comp. 32 (1978), 583-591. MR 58:10711
  • 20. Lawrence C. Washington, Introduction to cyclotomic fields, second ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, 1997. MR 97h:11130
  • 21. K. Wooldridge, Some results in arithmetical functions similar to Euler's phi-function, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1975.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40, 11Y60, 11Y16, 11R42, 11B68, 11R29, 94A60, 11R18

Retrieve articles in all journals with MSC (2000): 11Y40, 11Y60, 11Y16, 11R42, 11B68, 11R29, 94A60, 11R18

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

Keywords: Bernoulli numbers, irregular primes, zeta functions, quadratic extensions, cyclotomic extensions, class groups, computational number theory, cryptography
Received by editor(s): November 21, 2000
Received by editor(s) in revised form: September 16, 2002
Published electronically: July 28, 2003
Article copyright: © Copyright 2003 American Mathematical Society