Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Faster computation of the first factor of the class number of $ {\bf Q}(\zeta\sb p)$

Author: Vijay Jha
Journal: Math. Comp. 64 (1995), 1705-1710
MSC: Primary 11R18; Secondary 11R29, 11Y40
MathSciNet review: 1277768
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] R. P. Brent, Fast multiple precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), 242-251. MR 0395314 (52:16111)
  • [2] L. Carlitz and F. R. Olson, Maillet's determinant, Proc. Amer. Math. Soc. 6 (1955), 265-269. MR 0069207 (16:999d)
  • [3] 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 0121354 (22:12093)
  • [4] G. E. Collins, M. Mignotte, and F. Winkler, Arithmetic in basic algebraic domains, Computer Algebra Symbolic and Algebraic Computation (B. Buchberger, G. E. Collins, and R. Loos, eds.), Springer-Verlag, New York, 1982, pp. 189-220. MR 728973
  • [5] G. Cornell and M. Rosen, Group-theoretic constraints on the structure of the class group, J. Number Theory 13 (1981), 1-11. MR 602445 (82e:12005)
  • [6] H. Davenport, Multiplicative number theory, 2nd ed., Springer-Verlag, New York, 1980. MR 606931 (82m:10001)
  • [7] G. Fung, A. Granville, and H. C. Williams, Computation of the first factor of the class number of cyclotomic fields (to appear). MR 1189508 (93k:11097)
  • [8] F. Gerth, The ideal class group of two cyclotomic fields, Proc. Amer. Math. Soc. 78 (1980), 321-322. MR 553367 (80k:12004)
  • [9] E. Horowitz and S. Sahni, Fundamentals of computer algorithms, Galgotia Publications, New Delhi, India, 1988, pp. 422-458.
  • [10] K. Iwasawa, A note on ideal class groups, Nagoya Math. J. 27 (1966), 239-247. MR 0197438 (33:5603)
  • [11] T. Kimura and K. Horie, On the Stickelberger ideal and the relative class number, Trans. Amer. Math. Soc. 302 (1987), 727-739. MR 891643 (88f:11103)
  • [12] D. H. Lehmer and J. M. Masley, Table of the cyclotomic class number and their factors for $ 200 < p < 521$, Math. Comp. 32 (1978), 577-582. MR 0498484 (58:16594a)
  • [13] M. Newman, A table of the first factor for prime cyclotomic fields, Math. Comp. 24 (1970), 215-219. MR 0257029 (41:1684)
  • [14] F. P. Preparata and D. V. Sarvate, Computational complexity of Fourier tranforms over finite fields, Math. Comp. 31 (1977), 740-751. MR 0436662 (55:9603)
  • [15] P. Ribenboim, The book of prime number records, Springer-Verlag, New York, 1989. MR 1016815 (90g:11127)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R18, 11R29, 11Y40

Retrieve articles in all journals with MSC: 11R18, 11R29, 11Y40

Additional Information

Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society