A fast algorithm for polynomial factorization over ℚ p

David Ford; Sebastian Pauli; Xavier-François Roblot

Journal de théorie des nombres de Bordeaux (2002)

  • Volume: 14, Issue: 1, page 151-169
  • ISSN: 1246-7405

Abstract

top
We present an algorithm that returns a proper factor of a polynomial Φ ( x ) over the p -adic integers ℤ p (if Φ ( x ) is reducible over ℚ p ) or returns a power basis of the ring of integers of ℚ p [ x ] / Φ ( x ) ℚ p [ x ] (if Φ ( x ) is irreducible over ℚ p ). Our algorithm is based on the Round Four maximal order algorithm. Experimental results show that the new algorithm is considerably faster than the Round Four algorithm.

How to cite

top

Ford, David, Pauli, Sebastian, and Roblot, Xavier-François. "A fast algorithm for polynomial factorization over $\mathbb {Q}_p$." Journal de théorie des nombres de Bordeaux 14.1 (2002): 151-169. <http://eudml.org/doc/248904>.

@article{Ford2002,
abstract = {We present an algorithm that returns a proper factor of a polynomial $\Phi (x)$ over the $p$-adic integers $\mathbb \{Z\}_p$ (if $\Phi (x)$ is reducible over $\mathbb \{Q\}_p$) or returns a power basis of the ring of integers of $\mathbb \{Q\}_p[x]/ \Phi (x) \mathbb \{Q\}_p[x]$ (if $\Phi (x)$ is irreducible over $\mathbb \{Q\}_p$). Our algorithm is based on the Round Four maximal order algorithm. Experimental results show that the new algorithm is considerably faster than the Round Four algorithm.},
author = {Ford, David, Pauli, Sebastian, Roblot, Xavier-François},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {-adic integers; polynomial factorization},
language = {eng},
number = {1},
pages = {151-169},
publisher = {Université Bordeaux I},
title = {A fast algorithm for polynomial factorization over $\mathbb \{Q\}_p$},
url = {http://eudml.org/doc/248904},
volume = {14},
year = {2002},
}

TY - JOUR
AU - Ford, David
AU - Pauli, Sebastian
AU - Roblot, Xavier-François
TI - A fast algorithm for polynomial factorization over $\mathbb {Q}_p$
JO - Journal de théorie des nombres de Bordeaux
PY - 2002
PB - Université Bordeaux I
VL - 14
IS - 1
SP - 151
EP - 169
AB - We present an algorithm that returns a proper factor of a polynomial $\Phi (x)$ over the $p$-adic integers $\mathbb {Z}_p$ (if $\Phi (x)$ is reducible over $\mathbb {Q}_p$) or returns a power basis of the ring of integers of $\mathbb {Q}_p[x]/ \Phi (x) \mathbb {Q}_p[x]$ (if $\Phi (x)$ is irreducible over $\mathbb {Q}_p$). Our algorithm is based on the Round Four maximal order algorithm. Experimental results show that the new algorithm is considerably faster than the Round Four algorithm.
LA - eng
KW - -adic integers; polynomial factorization
UR - http://eudml.org/doc/248904
ER -

References

top
  1. [1] A. Ash, R. Pinch, R. Taylor, An Â4 extension of Q attached to a non-selfdual automorphic form on GL(3). Math. Annalen291 (1991), 753-766. Zbl0713.11036MR1135542
  2. [2] G. Baier, Zum Round 4 Algorithmus, Diplomarbeit, Technische Universität Berlin, 1996, http://www.math.TU-Berlin.DE/-kant/publications/diplom/baier.ps.gz. 
  3. [3] H. Cohen, Personal communication, 1996. 
  4. [4] D. Ford, P. Letard, Implementing the Round Four maximal order algorithm. J. Théor. Nombres Bordeaux6 (1994) 39-80, http://almira.math.u-bordeaux.fr:80/jtnb/1994-1/jtnb6-1.html. Zbl0817.11064MR1305287
  5. [5] E. HallouinCalcul de fermeture intégrale en dimension 1 et factorisation. Thèse, Université de Poitiers, 1998. 
  6. [6] W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers (second edition). Springer-Verlag, Berlin, 1990. Zbl0717.11045MR1055830
  7. [7] S. Pauli, Factoring Polynomials over Local Fields. Journal of Symbolic Computation, accepted 2001. Zbl1085.12500MR1858009
  8. [8] X.-R. Roblot, Algorithmes de factorisation dans les extensions relatives et applications de la conjecture de Stark à la construction des corps de classes de rayon. Thèse, Université BordeauxI, 1997, http://www.desargues.univ-lyon1.fr/home/roblot/papers.htm#1. 
  9. [9] E. Weiss, Algebraic number theory. McGraw-Hill, 1963. Zbl0115.03601MR159805

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.