Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Recognizing units in number fields

Author: Guoqiang Ge
Journal: Math. Comp. 63 (1994), 377-387
MSC: Primary 11Y40; Secondary 11R27
MathSciNet review: 1242057
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a deterministic polynomial-time algorithm that decides whether a power product $ \prod\nolimits_{i = 1}^k {\gamma _i^{{n_i}}} $ is a unit in the ring of integers of K, where K is a number field, $ {\gamma _i}$ are nonzero elements of K and $ {n_i}$ are rational integers. The main algorithm is based on the factor refinement method for ideals, which might be of independent interest.

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

  • [1] M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley, Reading, Mass., 1969. MR 0242802 (39:4129)
  • [2] E. Bach, J. Driscoll, and J. O. Shallit, Factor refinement, J. Algorithms 15 (1993), 199-222. MR 1231441 (94m:11148)
  • [3] Z. Borevich and I. Shafarevich, Number theory, Pure and Appl. Math., vol. 20, Academic Press, New York, 1966. MR 0195803 (33:4001)
  • [4] J. A. Buchmann and H. W. Lenstra, Jr., Approximating rings of integers in number fields, in preparation.
  • [5] J. W. S. Cassels and A. Fröhlich, Algebraic number theory, Academic Press, London, 1967. MR 0215665 (35:6500)
  • [6] A. L. Chistov, The complexity of constructing the ring of integers of a global field, Soviet Math. Dokl. 39 (1989), 597-600. MR 1014763 (90g:11170)
  • [7] J. L. Hafner and K. S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068-1083. MR 1135749 (93d:15021)
  • [8] S. Lang, Algebraic number theory, Graduate Texts in Math., vol. 110, Springer-Verlag, New York, 1986. MR 1282723 (95f:11085)
  • [9] H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), 211-244. MR 1129315 (93g:11131)
  • [10] H. Matsumura, Commutative ring theory, Cambridge Studies in Advanced Math., vol. 8, Cambridge Univ. Press, New York, 1986. MR 879273 (88h:13001)
  • [11] A. Schrijver, Theory of linear and integer programming, Wiley, Chichester, NY, 1986. MR 874114 (88m:90090)
  • [12] E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963. MR 0159805 (28:3021)

Similar Articles

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

Retrieve articles in all journals with MSC: 11Y40, 11R27

Additional Information

Keywords: Number field, units, algorithm
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society