Recognizing units in number fields
HTML articles powered by AMS MathViewer
- by Guoqiang Ge PDF
- Math. Comp. 63 (1994), 377-387 Request permission
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
- M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0242802
- Eric Bach, James Driscoll, and Jeffrey Shallit, Factor refinement, J. Algorithms 15 (1993), no. 2, 199–222. MR 1231441, DOI 10.1006/jagm.1993.1038
- A. I. Borevich and I. R. Shafarevich, Number theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. Translated from the Russian by Newcomb Greenleaf. MR 0195803 J. A. Buchmann and H. W. Lenstra, Jr., Approximating rings of integers in number fields, in preparation.
- J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Academic Press, London; Thompson Book Co., Inc., Washington, D.C., 1967. MR 0215665
- A. L. Chistov, The complexity of the construction of the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), no. 5, 1063–1067 (Russian); English transl., Soviet Math. Dokl. 39 (1989), no. 3, 597–600. MR 1014763
- James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083. MR 1135749, DOI 10.1137/0220067
- Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
- H. W. Lenstra Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211–244. MR 1129315, DOI 10.1090/S0273-0979-1992-00284-7
- Hideyuki Matsumura, Commutative ring theory, Cambridge Studies in Advanced Mathematics, vol. 8, Cambridge University Press, Cambridge, 1986. Translated from the Japanese by M. Reid. MR 879273
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- Edwin Weiss, Algebraic number theory, McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London, 1963. MR 0159805
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp. 63 (1994), 377-387
- MSC: Primary 11Y40; Secondary 11R27
- DOI: https://doi.org/10.1090/S0025-5718-1994-1242057-X
- MathSciNet review: 1242057