Recognizing units in number fields
Author:
Guoqiang Ge
Journal:
Math. Comp. 63 (1994), 377387
MSC:
Primary 11Y40; Secondary 11R27
MathSciNet review:
1242057
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We present a deterministic polynomialtime algorithm that decides whether a power product is a unit in the ring of integers of K, where K is a number field, are nonzero elements of K and are rational integers. The main algorithm is based on the factor refinement method for ideals, which might be of independent interest.
 [1]
M.
F. Atiyah and I.
G. Macdonald, Introduction to commutative algebra,
AddisonWesley Publishing Co., Reading, Mass.LondonDon Mills, Ont., 1969.
MR
0242802 (39 #4129)
 [2]
Eric
Bach, James
Driscoll, and Jeffrey
Shallit, Factor refinement, J. Algorithms 15
(1993), no. 2, 199–222. MR 1231441
(94m:11148), http://dx.doi.org/10.1006/jagm.1993.1038
 [3]
A.
I. Borevich and I.
R. Shafarevich, Number theory, Translated from the Russian by
Newcomb Greenleaf. Pure and Applied Mathematics, Vol. 20, Academic Press,
New YorkLondon, 1966. MR 0195803
(33 #4001)
 [4]
J. A. Buchmann and H. W. Lenstra, Jr., Approximating rings of integers in number fields, in preparation.
 [5]
Algebraic number theory, Proceedings of an instructional
conference organized by the London Mathematical Society (a NATO Advanced
Study Institute) with the support of the Inter national Mathematical Union.
Edited by J. W. S. Cassels and A. Fröhlich, Academic Press, London;
Thompson Book Co., Inc., Washington, D.C., 1967. MR 0215665
(35 #6500)
 [6]
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
(90g:11170)
 [7]
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
(93d:15021), http://dx.doi.org/10.1137/0220067
 [8]
Serge
Lang, Algebraic number theory, 2nd ed., Graduate Texts in
Mathematics, vol. 110, SpringerVerlag, New York, 1994. MR 1282723
(95f:11085)
 [9]
H.
W. Lenstra Jr., Algorithms in algebraic number
theory, Bull. Amer. Math. Soc. (N.S.)
26 (1992), no. 2,
211–244. MR 1129315
(93g:11131), http://dx.doi.org/10.1090/S027309791992002847
 [10]
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
(88h:13001)
 [11]
Alexander
Schrijver, Theory of linear and integer programming,
WileyInterscience Series in Discrete Mathematics, John Wiley & Sons,
Ltd., Chichester, 1986. A WileyInterscience Publication. MR 874114
(88m:90090)
 [12]
Edwin
Weiss, Algebraic number theory, McGrawHill Book Co., Inc.,
New YorkSan FranciscoTorontoLondon, 1963. MR 0159805
(28 #3021)
 [1]
 M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, AddisonWesley, Reading, Mass., 1969. MR 0242802 (39:4129)
 [2]
 E. Bach, J. Driscoll, and J. O. Shallit, Factor refinement, J. Algorithms 15 (1993), 199222. 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), 597600. MR 1014763 (90g:11170)
 [7]
 J. L. Hafner and K. S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 10681083. MR 1135749 (93d:15021)
 [8]
 S. Lang, Algebraic number theory, Graduate Texts in Math., vol. 110, SpringerVerlag, 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), 211244. 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, McGrawHill, 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
DOI:
http://dx.doi.org/10.1090/S0025571819941242057X
PII:
S 00255718(1994)1242057X
Keywords:
Number field,
units,
algorithm
Article copyright:
© Copyright 1994
American Mathematical Society
