Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields
Journal de Théorie des Nombres de Bordeaux, Tome 23 (2011) no. 3, pp. 667-696.

Nous présentons un algorithme pour calculer le discriminant et la décomposition des idéaux d’un corps de nombres en produit d’idéaux premiers. L’algorithme est un raffinement d’une méthode de factorisation p-adique qui utilise polygones de Newton d’ordre supérieur. L’exigence de mémoire et les temps d’exécution sont très bons.

We present an algorithm for computing discriminants and prime ideal decomposition in number fields. The algorithm is a refinement of a p-adic factorization method based on Newton polygons of higher order. The running-time and memory requirements of the algorithm appear to be very good.

Reçu le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.782
@article{JTNB_2011__23_3_667_0,
     author = {Jordi Gu\`ardia and Jes\'us Montes and Enric Nart},
     title = {Higher {Newton} polygons in the computation of discriminants and prime ideal decomposition in number fields},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {667--696},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {23},
     number = {3},
     year = {2011},
     doi = {10.5802/jtnb.782},
     zbl = {1266.11131},
     mrnumber = {2861080},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.782/}
}
Jordi Guàrdia; Jesús Montes; Enric Nart. Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. Journal de Théorie des Nombres de Bordeaux, Tome 23 (2011) no. 3, pp. 667-696. doi : 10.5802/jtnb.782. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.782/

[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. | Numdam | MR 1360644 | Zbl 0828.11075

[2] H. Cohen, A course in Computational Number Theory. Graduate Texts in Mathematics, vol. 138, Springer V., Berlin, 2000, fourth printing. | MR 1728313

[3] D. Ford, The construction of maximal orders over a Dedekind domain. Journal of Symbolic Computation 4 (1987), 69–75. | MR 908413 | 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. | Numdam | MR 1305287 | Zbl 0817.11064

[5] D. Ford, S. Pauli, X. Roblot, A fast algorithm for polynomial factorization over p . J. Théorie des Nombres de Bordeaux 14 (2002), no. 1, 151–169. | Numdam | MR 1925995 | 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. | MR 2721420 | Zbl pre05793679

[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. | MR 2833586

[8] J. Guàrdia, J. Montes, E. Nart, Higher Newton polygons and integral bases. ArXiv: 0902.3428v2 [math.NT].

[9] J. Guàrdia, J. Montes, E. Nart, Okutsu invariants and Newton polygons. Acta Arithmetica 145 (2010), 83–108. | MR 2719575 | Zbl pre05834843

[10] J. Guàrdia, J. Montes, E. Nart, A new computational approach to ideal theory in number fields. ArXiv:1005.1156v3 [math.NT].

[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].

[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. | MR 649064 | 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. | MR 2721428 | Zbl pre05793687

[15] H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung. Funktionalanalysis, Approximationstheorie, Numerische Mathematik (Oberwolfach, 1965), Birkhäuser, Basel, 1967, 90–103. | MR 227135 | 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. | MR 371862 | Zbl 0248.12011