staple
With cedram.org

Search the site

Table of contents for this issue | Previous article | Next article
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, 23 no. 3 (2011), p. 667-696, doi: 10.5802/jtnb.782
Article PDF | Reviews MR 2861080 | Zbl 1266.11131 | 1 citation in Cedram

Résumé - Abstract

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.

Bibliography

[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. Cedram |  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. Cedram |  MR 1305287 |  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. Cedram |  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