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 -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 -adic factorization method based on Newton polygons of higher order. The running-time and memory requirements of the algorithm appear to be very good.
@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, Tome 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 . 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
Cité par Sources :
