On factor refinement in number fields

Authors:
Johannes Buchmann and Friedrich Eisenbrand

Journal:
Math. Comp. **68** (1999), 345-350

MSC (1991):
Primary 11Y40, 11R27, 11R04, 11Y16

MathSciNet review:
1613766

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be an order of an algebraic number field. It was shown by Ge that given a factorization of an -ideal into a product of -ideals it is possible to compute in polynomial time an overorder of and a *gcd-free* refinement of the input factorization; i.e., a factorization of into a power product of -ideals such that the bases of that power product are all invertible and pairwise coprime and the extensions of the factors of the input factorization are products of the bases of the output factorization. In this paper we prove that the order is the smallest overorder of in which such a gcd-free refinement of the input factorization exists. We also introduce a partial ordering on the gcd-free factorizations and prove that the factorization which is computed by Ge's algorithm is the smallest gcd-free refinement of the input factorization with respect to this partial ordering.

**[BDS93]**Eric Bach, James Driscoll, and Jeffrey Shallit,*Factor refinement*, J. Algorithms**15**(1993), no. 2, 199–222. MR**1231441**, 10.1006/jagm.1993.1038**[Ge93]**Guoqiang Ge,*Algorithms related to multiplicative representations of algebraic numbers*, PhD thesis, U.C. Berkeley, 1993.**[Ge94]**Guoqiang Ge,*Recognizing units in number fields*, Math. Comp.**63**(1994), no. 207, 377–387. MR**1242057**, 10.1090/S0025-5718-1994-1242057-X**[ZS58]**Oscar Zariski and Pierre Samuel,*Commutative algebra, Volume I*, The University Series in Higher Mathematics, D. Van Nostrand Company, Inc., Princeton, New Jersey, 1958. With the cooperation of I. S. Cohen. MR**0090581**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11Y40,
11R27,
11R04,
11Y16

Retrieve articles in all journals with MSC (1991): 11Y40, 11R27, 11R04, 11Y16

Additional Information

**Johannes Buchmann**

Affiliation:
Technische Hochschule Darmstadt, Alexanderstr. 10, D-64283 Darmstadt, Germany

Email:
buchmann@cdc.informatik.th-darmstadt.de

**Friedrich Eisenbrand**

Affiliation:
Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany

Email:
eisen@mpi-sb.mpg.de

DOI:
http://dx.doi.org/10.1090/S0025-5718-99-01023-6

Received by editor(s):
November 21, 1996

Article copyright:
© Copyright 1999
American Mathematical Society