scientific article; zbMATH DE number 1075583

Publication date 16 October 1997

\((S)\)-unit group complexity analysis enumeration algorithm lattices over number fields norm equations reduction algorithm relative extensions relative units

Mathematics Subject Classification ID

Multiplicative and norm form equations (11D57) Units and factorization (11R27) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40)

Review text

Continuing the work of \textit{A. Jurk} [Über die Berechnung von Lösungen relativer Normgleichungen in algebraischen Zahlkörpern, Diss. Univ. Düsseldorf (1993; Zbl 0848.11064)], the author completely generalizes the algorithm of \textit{U. Fincke} [Ein Ellipsoidverfahren zur Lösung von Normgleichungen in algebraischen Zahlkörpern, Diss. Univ. Düsseldorf (1984; Zbl 0559.10012)] to relative extensions, i.e. instead of looking for solutions to \(N(x)=k\in\mathbb Z\) with \(x\) an element of an extension of \(\mathbb Q\), he examines solutions of \(N(x)=\theta \in\mathbb F\) for a number field \(\mathbb F\) and \(x\) an element of \(o_{\mathbb K}\), the number ring of an extension \(\mathbb K\) of \(\mathbb F\). In the first part of his work, the author gives some results on the (\(S\)-)unit group of such fields, with special emphasis on the so called relative units, units having relative norm \(1\). He is able to get relations between the regulator similar to those in [\textit{A.-M. Bergé} and \textit{J. Martinet}, Semin. Theor. Nombres, Paris/Fr. 1987-88, Prog. Math. 81, 23-50 (1990; Zbl 0699.12014)]. To utilize this for practical computations, he includes a lower bound on the regulator. Since Fincke's algorithm makes use of lattice techniques, the author investigates lattices over number fields in the next part of his work. Using [\textit{P. Humbert}, Comment. Math. Helv. 12, 263-306 (1940; Zbl 0023.19905)] he is able to give an enumeration and reduction algorithm (similar to the LLL-algorithm) in this case. Unfortunately, his reduction procedure yields no bounds on the length of the reduced basis [\textit{C. Fieker} and \textit{M. E. Pohst}, Lect. Notes Comput. Sci. 1122, 133-139 (1996)]. In the next part, this geometric setting is applied to solve norm equations. Similar to Jurk he shows that a complete set of representatives for the solutions are among the points in finitely many ellipsoids. Those can be found effectively with the methods of the other parts. Next, using ideas of \textit{D. A. Garbanati} [J. Reine Angew. Math. 316, 1-13 (1980; Zbl 0421.12002)] he attacks the problem of solutions in the number field opposed to solutions in the number ring. He concludes this chapter with an (algebraic) complexity analysis, relating the amount of work to do to the invariants of the fields involved and the size of the right hand size. In addition he demonstrates that, at least for solutions in the number field, methods based on the \(S\)-units are much more efficient than the geometric approach. As part of his work, the author implemented all these algorithms as part of the KANT-package [\textit{M. Daberkow} et al., J. Symb. Comput. 24, 267-283 (1997; Zbl 0886.11070)] which is available from ftp://ftp.math.TU-Berlin.DE/pub/algebra/Kant/Kash/.

Recommendations

Cited in

(17)

Describes a project that uses

Uses Software

KANT/KASH

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359498)