Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Comparison of algorithms to calculate quadratic irregularity of prime numbers

Author: Joshua Holden
Journal: Math. Comp. 71 (2002), 863-871
MSC (2000): Primary 11Y40, 11Y60, 11Y16, 11B68; Secondary 11R42, 11R29, 94A60, 11R18
Published electronically: August 3, 2001
MathSciNet review: 1885634
Full-text PDF

Abstract | References | Similar Articles | Additional Information


In previous work, the author has extended the concept of regular and irregular primes to the setting of arbitrary totally real number fields $k_{0}$, using the values of the zeta function $\zeta_{k_{0}}$at negative integers as our ``higher Bernoulli numbers''. In the case where $k_{0}$ is a real quadratic field, Siegel presented two formulas for calculating these zeta-values: one using entirely elementary methods and one which is derived from the theory of modular forms. (The author would like to thank Henri Cohen for suggesting an analysis of the second formula.) We briefly discuss several algorithms based on these formulas and compare the running time involved in using them to determine the index of $k_{0}$-irregularity (more generally, ``quadratic irregularity'') of a prime number.

References [Enhancements On Off] (What's this?)

  • 1. Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, Springer-Verlag, 1976. MR 55:7892
  • 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, <>, <ftp://megrez.->.
  • 3. 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.
  • 4. Henri Cohen, Sums involving the values at negative integers of ${L}$-functions of quadratic characters, Math. Ann. 217 (1975), 271-285. MR 52:10615
  • 5. -, Variations sur un thème de Siegel et Hecke, Acta Arith. 30 (1976), 63-93. MR 54:10207
  • 6. 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
  • 7. -, On the Fontaine-Mazur conjecture for number fields and an analogue for function fields, Ph.D. thesis, Brown University, 1998.
  • 8. -, On the Fontaine-Mazur Conjecture for number fields and an analogue for function fields, J. Number Theory 81 (2000), 16-47. MR 2001e:11111
  • 9. -, First-hit analysis of algorithms for computing quadratic irregularity, (In preparation).
  • 10. Carl Ludwig Siegel, Bernoullische Polynome und quadratische Zahlkörper, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 2 (1968), 7-38. MR 38:2123
  • 11. Don Zagier, On the values at negative integers of the zeta-function of a real quadratic field, Enseign. Math. (2) 22 (1976), 55-95. MR 53:10742

Similar Articles

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

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

Additional Information

Joshua Holden
Affiliation: Department of Mathematics and Statistics, University of Massachusetts at Amherst, Amherst, Massachusetts 01003
Address at time of publication: Department of Mathematics, Rose-Hulman Institute of Technology, 5500 Wabash Ave., Terre Haute, Indiana 47803

Keywords: Bernoulli numbers, Bernoulli polynomials, irregular primes, zeta functions, quadratic extensions, cyclotomic extensions, class groups, cryptography
Received by editor(s): July 23, 1999
Received by editor(s) in revised form: August 8, 2000
Published electronically: August 3, 2001
Article copyright: © Copyright 2001 American Mathematical Society