Comparison of algorithms to calculate quadratic irregularity of prime numbers

Holden, Joshua

doi:10.1090/S0025-5718-01-01341-2

Comparison of algorithms to calculate quadratic irregularity of prime numbers
HTML articles powered by AMS MathViewer

by Joshua Holden PDF

Math. Comp. 71 (2002), 863-871 Request permission

Abstract:

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

Tom M. Apostol, Introduction to analytic number theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976. MR 0434929
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://hasse.mathematik.tu-muenchen.de/ntsw/pari/Welcome.html, ftp://megrez.-math.u-bordeaux.fr.
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.
Henri Cohen, Sums involving the values at negative integers of $L$ functions of quadratic characters, Séminaire de Théorie des Nombres, 1974-1975 (Univ. Bordeaux I, Talence), Exp. No. 3, Lab. Théorie des Nombres, Centre Nat. Recherche Sci., Talence, 1975, pp. 21. MR 0389784
Henri Cohen, Variations sur un thème de Seigel et Hecke, Acta Arith. 30 (1976/77), no. 1, 63–93 (French). MR 422215, DOI 10.4064/aa-30-1-63-93
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
—, On the Fontaine-Mazur conjecture for number fields and an analogue for function fields, Ph.D. thesis, Brown University, 1998.
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
—, First-hit analysis of algorithms for computing quadratic irregularity, (In preparation).
Carl Ludwig Siegel, Bernoullische Polynome und quadratische Zahlkörper, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1968 (1968), 7–38 (German). MR 233802
Don Zagier, On the values at negative integers of the zeta-function of a real quadratic field, Enseign. Math. (2) 22 (1976), no. 1-2, 55–95. MR 406957