Recognizing units in number fields

Ge, Guoqiang

doi:10.1090/S0025-5718-1994-1242057-X

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

Approximating rings of integers in number fields

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