Faster computation of the first factor of the class number of 𝑄(𝜁_{𝑝})

Jha, Vijay

doi:10.1090/S0025-5718-1995-1277768-4

Faster computation of the first factor of the class number of $\textbf {Q}(\zeta _ p)$
HTML articles powered by AMS MathViewer

by Vijay Jha PDF

Math. Comp. 64 (1995), 1705-1710 Request permission

Abstract:

We describe two fast methods for computing the first factor of the class number of the cyclotomic field $\mathbb {Q}({\zeta _p})$ in $\mathcal {O}({p^2}{\log ^5}p)$ and $\mathcal {O}({p^2}\log p)$ steps of elementary arithmetic operations on the numbers of size p, respectively. The first is deterministic, while the second holds under the GRH. This is an improvement over the previous method of Lehmer and Masley, which has complexity $\mathcal {O}({p^{3.81}})$.

References

Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI 10.1145/321941.321944
L. Carlitz and F. R. Olson, Maillet’s determinant, Proc. Amer. Math. Soc. 6 (1955), 265–269. MR 69207, DOI 10.1090/S0002-9939-1955-0069207-2
L. Carlitz, A generalization of Maillet’s determinant and a bound for the first factor of the class number, Proc. Amer. Math. Soc. 12 (1961), 256–261. MR 121354, DOI 10.1090/S0002-9939-1961-0121354-5
G. E. Collins, M. Mignotte, and F. Winkler, Arithmetic in basic algebraic domains, Computer algebra, Springer, Vienna, 1983, pp. 189–220. MR 728973
Gary Cornell and Michael Rosen, Group-theoretic constraints on the structure of the class group, J. Number Theory 13 (1981), no. 1, 1–11. MR 602445, DOI 10.1016/0022-314X(81)90026-3
Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931, DOI 10.1007/978-1-4757-5927-3
Gilbert Fung, Andrew Granville, and Hugh C. Williams, Computation of the first factor of the class number of cyclotomic fields, J. Number Theory 42 (1992), no. 3, 297–312. MR 1189508, DOI 10.1016/0022-314X(92)90095-7
Frank Gerth III, The ideal class groups of two cyclotomic fields, Proc. Amer. Math. Soc. 78 (1980), no. 3, 321–322. MR 553367, DOI 10.1090/S0002-9939-1980-0553367-5

Fundamentals of computer algorithms

Kenkichi Iwasawa, A note on ideal class groups, Nagoya Math. J. 27 (1966), 239–247. MR 197438, DOI 10.1017/S0027763000012046
Tatsuo Kimura and Kuniaki Horie, On the Stickelberger ideal and the relative class number, Trans. Amer. Math. Soc. 302 (1987), no. 2, 727–739. MR 891643, DOI 10.1090/S0002-9947-1987-0891643-8
D. H. Lehmer and J. M. Masley, Table of the cyclotomic class numbers $h^*(p)$ and their factors for $200<p<521$, Math. Comp. 32 (1978), no. 142, 577–582. MR 498484, DOI 10.1090/S0025-5718-1978-0498484-2
Morris Newman, A table of the first factor for prime cyclotomic fields, Math. Comp. 24 (1970), 215–219. MR 257029, DOI 10.1090/S0025-5718-1970-0257029-5
F. P. Preparata and D. V. Sarwate, Computational complexity of Fourier transforms over finite fields, Math. Comp. 31 (1977), no. 139, 740–751. MR 436662, DOI 10.1090/S0025-5718-1977-0436662-8
Paulo Ribenboim, The book of prime number records, 2nd ed., Springer-Verlag, New York, 1989. MR 1016815, DOI 10.1007/978-1-4684-0507-1