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

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.

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.

DOI: 10.5802/jtnb.782
Guàrdia, Jordi 1; Montes, Jesús 2; Nart, Enric 3

1 Departament de Matemàtica Aplicada IV Escola Politècnica Superior d’Enginyera de Vilanova i la Geltrú Av. Víctor Balaguer s/n. E-08800 Vilanova i la Geltrú, Catalonia
2 Departament de Ciències Econòmiques i Empresarials Facultat de Ciències Socials, Universitat Abat Oliba CEU Bellesguard 30 E-08022 Barcelona, Catalonia, Spain Departament de Matemàtica Econòmica, Financera i Actuarial Facultat d’Economia i Empresa, Universitat de Barcelona Av. Diagonal 690 E-08034 Barcelona, Catalonia, Spain
3 Departament de Matemàtiques Universitat Autònoma de Barcelona Edifici C E-08193 Bellaterra, Barcelona, Catalonia, Spain
@article{JTNB_2011__23_3_667_0,
     author = {Gu\`ardia, Jordi and Montes, Jes\'us and Nart, Enric},
     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 = {http://archive.numdam.org/articles/10.5802/jtnb.782/}
}
TY  - JOUR
AU  - Guàrdia, Jordi
AU  - Montes, Jesús
AU  - Nart, Enric
TI  - Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2011
SP  - 667
EP  - 696
VL  - 23
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - http://archive.numdam.org/articles/10.5802/jtnb.782/
DO  - 10.5802/jtnb.782
LA  - en
ID  - JTNB_2011__23_3_667_0
ER  - 
%0 Journal Article
%A Guàrdia, Jordi
%A Montes, Jesús
%A Nart, Enric
%T Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields
%J Journal de théorie des nombres de Bordeaux
%D 2011
%P 667-696
%V 23
%N 3
%I Société Arithmétique de Bordeaux
%U http://archive.numdam.org/articles/10.5802/jtnb.782/
%R 10.5802/jtnb.782
%G en
%F JTNB_2011__23_3_667_0
Guàrdia, Jordi; Montes, Jesús; Nart, Enric. Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields. Journal de théorie des nombres de Bordeaux, Volume 23 (2011) no. 3, pp. 667-696. doi : 10.5802/jtnb.782. http://archive.numdam.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 | Zbl

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

[3] D. Ford, The construction of maximal orders over a Dedekind domain. Journal of Symbolic Computation 4 (1987), 69–75. | MR | Zbl

[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 | Zbl

[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 | Zbl

[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

[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

[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

[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 | Zbl

[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

[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 | Zbl

[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 | Zbl

Cited by Sources: