Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields (Q449717)

Let \(K\) be a number field, let \(\alpha\) be an element of the ring of integers \({\mathbb Z}_K\) of \(K\) such that \(K={\mathbb Q}(\alpha)\), and let \(f(X)\in{\mathbb Z}[X]\) be the minimum polynomial of \(\alpha\) over \(\mathbb Q\). A basic problem in computational number theory is determining the factorization of \(p{\mathbb Z}_K\) into prime ideals. This paper describes an algorithm for computing this factorization in terms of \(f(X)\). The algorithm is based on the theory of higher order Newton polygons which was described in [Trans. Am. Math. Soc. 364, No. 1, 361--416 (2012; Zbl 1252.11091)]; in this paper the procedures from the cited article are refined to improve the running time. The algorithm produces generators for each of the prime ideals in \({\mathbb Z}_K\) lying over \(p{\mathbb Z}\), and expresses \(p{\mathbb Z}_K\) as a product of powers of these ideals. It also determines the \(p\)-adic valuation of the index of \({\mathbb Z}[\alpha]\) in \({\mathbb Z}_K\), and thus gives a method for computing the discriminant of \(K\). The procedures that are described here have been implemented by the authors and applied successfully in some examples involving number fields of fairly high degree.