×

Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. (English. French summary) Zbl 1266.11131

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.

MSC:

11Y40 Algebraic number theory computations
11R09 Polynomials (irreducibility, etc.)
11R29 Class numbers, class groups, discriminants
11S15 Ramification and extension theory
11S05 Polynomials
11R04 Algebraic numbers; rings of algebraic integers

Citations:

Zbl 1252.11091
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] J.A. Buchmann, H.W. Lenstra, Approximating ring of integers in number fields. J. Théorie des Nombres de Bordeaux 6 (1994), no. 2, 221-260. · Zbl 0828.11075
[2] H. Cohen, A course in Computational Number Theory. Graduate Texts in Mathematics, vol. 138, Springer V., Berlin, 2000, fourth printing. · Zbl 0945.11001
[3] D. Ford, The construction of maximal orders over a Dedekind domain. Journal of Symbolic Computation 4 (1987), 69-75. · Zbl 0632.13003
[4] D. Ford, P. Letard, Implementing the Round Four maximal order algorithm. J. Théorie des Nombres de Bordeaux 6 (1994), no. 1, 39-80. · Zbl 0817.11064
[5] D. Ford, S. Pauli, X. Roblot, A fast algorithm for polynomial factorization over \(\mathbb{Q}_p\). J. Théorie des Nombres de Bordeaux 14 (2002), no. 1, 151-169. · Zbl 1032.11053
[6] D. Ford, O. Veres, On the Complexity of the Montes Ideal Factorization Algorithm. In G. Hanrot and F. Morain and E. Thomé, Algorithmic Number Theory, 9th International Symposium, ANTS-IX, Nancy, France, July 19-23, 2010, LNCS, Springer Verlag 2010. · Zbl 1260.11085
[7] J. Guàrdia, J. Montes, E. Nart, Newton polygons of higher order in algebraic number theory. Trans. Amer. Math. Soc. 364 (2012), no. 1, 361-416. · Zbl 1252.11091
[8] J. Guàrdia, J. Montes, E. Nart, Higher Newton polygons and integral bases. ArXiv: 0902.3428v2 [math.NT]. · Zbl 1394.11071
[9] J. Guàrdia, J. Montes, E. Nart, Okutsu invariants and Newton polygons. Acta Arithmetica 145 (2010), 83-108. · Zbl 1266.11121
[10] J. Guàrdia, J. Montes, E. Nart, A new computational approach to ideal theory in number fields. ArXiv:1005.1156v3 [math.NT]. · Zbl 1287.11142
[11] J. Guàrdia, E. Nart, S. Pauli, Single-factor lifting and factorization of polynomials over local fields. Journal of Symbolic Computation, to appear, arXiv:1104.3181v1 [math.NT]. · Zbl 1262.11106
[12] J. Montes, Polígonos de Newton de orden superior y aplicaciones aritméticas. Tesi Doctoral, Universitat de Barcelona 1999.
[13] K. Okutsu, Construction of integral basis I, II. Proc. Japan Acad. 58 (1982), Ser. A, 47-49, 87-89. · Zbl 0526.13008
[14] S. Pauli, Factoring polynomials over local fields, II. In G. Hanrot and F. Morain and E. Thomé, Algorithmic Number Theory, 9th International Symposium, ANTS-IX, Nancy, France, July 19-23, 2010, LNCS, Springer Verlag 2010. · Zbl 1260.12005
[15] H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung. Funktionalanalysis, Approximationstheorie, Numerische Mathematik (Oberwolfach, 1965), Birkhäuser, Basel, 1967, 90-103. · Zbl 0153.36702
[16] H. Zassenhaus, On the Second Round or the Maximal Order Program. In Applications of number theory to numerical analysis, Academic Press, New York, 1972, 398-431. · Zbl 0248.12011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.