On computing subfields. A detailed description of the algorithm (Q1292617): Difference between revisions

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.