On computing subfields. A detailed description of the algorithm
type: Item
instance of: scholarly article
title: On computing subfields. A detailed description of the algorithm
zbMATH Open document ID: 0935.11047
author: Jürgen Klüners
published in: Journal de Théorie des Nombres de Bordeaux
publication date: 1999-06-23T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/93716
full work available at URL: jtnb10-2.html
review text: In this paper the author gives an efficient algorithm for the computation of all subfields of a given number field. This is a part of his Ph.D. thesis [\textit{J. Klüners}, ``On the computation of automorphisms and subfields of algebraic number fields'' (in German), Berlin: TU Berlin, FB 3 Mathematik (1997; Zbl 0912.11059)] and a continuation of the work of \textit{J. Klüners} and \textit{M. Pohst} [J. Symb. Comput. 24, 385-397 (1997; Zbl 0886.11072)]. The starting point of this algorithm is the bijection between subfields and certain block systems of the Galois group. By a careful analysis, the author develops several combinatorial properties of block systems, as well as properties connected to the \(p\)-adic factorization of a defining polynomial for the number field. The main algorithmic idea is to enumerate all systems that have the aforementioned properties and try to compute subfields from these ``potential block systems'' (as the author calls them). The most important technique is the use of certain unramified \(p\)-adic fields. In the second chapter the author therefore dicusses in great detail the algorithms of importance for him like Hensel- and Newton-lifting. In order to make this efficient he uses special representations for the used \(p\)-adic fields. In the later parts the author gives a wealth of details of his implementation that is immensly useful for anyone trying to implement this algorithm. He concludes by giving some (large) examples proving that this method is really efficient although worst-case-exponential in nature.
reviewed by: Claus Fieker
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 11R32
zbMATH DE Number: 1307384
zbMATH Keywords: subfields
zbMATH Keywords: block systems
describes a project that uses: KANT/KASH
MaRDI profile type: Publication
OpenAlex ID: W2328143117
cites work: Ideal decompositions and subfields
cites work: Q3726220
cites work: A polynomial reduction algorithm
cites work: Q3139838
cites work: Efficient rational number reconstruction
cites work: KANT V4
cites work: Imprimitive Ninth-Degree Number Fields with Small Discriminants
cites work: Q3348991
cites work: Block Systems of a Galois Group
cites work: Q4359499
cites work: On computing subfields
cites work: Factoring Polynomials over Algebraic Number Fields
cites work: Solvability by radicals is in polynomial time
cites work: Q3135187
cites work: An Inequality About Factors of Polynomials
cites work: Q4821147
cites work: Q4692759
cites work: Factoring Polynomials Over Algebraic Number Fields
cites work: Q5512231
DOI: 10.5802/JTNB.227
Recommended article: Block Systems of a Galois Group
Recommended article: Computing subfields of number fields and applications to Galois group computations
Recommended article: Q4359499
Recommended article: Generating subfields
Recommended article: Q3348991
Recommended article: The complexity of computing all subfields of an algebraic number field
Recommended article: Isomorphisms of algebraic number fields
Recommended article: Subexponential algorithms for class group and unit computations
Recommended article: Reducing number field defining polynomials: an application to class group computations
description: scientific article; zbMATH DE number 1307384