Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields

Jordi Guàrdia[1]; Jesús Montes[2]; Enric Nart[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

Journal de Théorie des Nombres de Bordeaux (2011)

  • Volume: 23, Issue: 3, page 667-696
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Guàrdia, Jordi, Montes, Jesús, and 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 23.3 (2011): 667-696. <http://eudml.org/doc/219682>.

@article{Guàrdia2011,
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.},
affiliation = {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; 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; Departament de Matemàtiques Universitat Autònoma de Barcelona Edifici C E-08193 Bellaterra, Barcelona, Catalonia, Spain},
author = {Guàrdia, Jordi, Montes, Jesús, Nart, Enric},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Newton polygons; discriminants; ideal decomposition},
language = {eng},
month = {11},
number = {3},
pages = {667-696},
publisher = {Société Arithmétique de Bordeaux},
title = {Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields},
url = {http://eudml.org/doc/219682},
volume = {23},
year = {2011},
}

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
DA - 2011/11//
PB - Société Arithmétique de Bordeaux
VL - 23
IS - 3
SP - 667
EP - 696
AB - 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.
LA - eng
KW - Newton polygons; discriminants; ideal decomposition
UR - http://eudml.org/doc/219682
ER -

References

top
  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. Zbl0828.11075MR1360644
  2. H. Cohen, A course in Computational Number Theory. Graduate Texts in Mathematics, vol. 138, Springer V., Berlin, 2000, fourth printing. MR1728313
  3. D. Ford, The construction of maximal orders over a Dedekind domain. Journal of Symbolic Computation 4 (1987), 69–75. Zbl0632.13003MR908413
  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. Zbl0817.11064MR1305287
  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. Zbl1032.11053MR1925995
  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. Zbl1260.11085MR2721420
  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. Zbl1252.11091MR2833586
  8. J. Guàrdia, J. Montes, E. Nart, Higher Newton polygons and integral bases. ArXiv: 0902.3428v2 [math.NT]. Zbl06371493
  9. J. Guàrdia, J. Montes, E. Nart, Okutsu invariants and Newton polygons. Acta Arithmetica 145 (2010), 83–108. Zbl1266.11121MR2719575
  10. J. Guàrdia, J. Montes, E. Nart, A new computational approach to ideal theory in number fields. ArXiv:1005.1156v3 [math.NT]. Zbl1287.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]. Zbl1262.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. Zbl0526.13008MR649064
  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. Zbl1260.12005MR2721428
  15. H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung. Funktionalanalysis, Approximationstheorie, Numerische Mathematik (Oberwolfach, 1965), Birkhäuser, Basel, 1967, 90–103. Zbl0153.36702MR227135
  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. Zbl0248.12011MR371862

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.