## 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
E. Horowitz and S. Sahni, - 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

*Fundamentals of computer algorithms*, Galgotia Publications, New Delhi, India, 1988, pp. 422-458.

## Additional Information

- © Copyright 1995 American Mathematical Society
- Journal: Math. Comp.
**64**(1995), 1705-1710 - MSC: Primary 11R18; Secondary 11R29, 11Y40
- DOI: https://doi.org/10.1090/S0025-5718-1995-1277768-4
- MathSciNet review: 1277768