A fast algorithm for polynomial factorization over ℚp
Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 1, pp. 151-169.

Dans cet article, nous présentons un algorithme qui retourne pour un polynôme Φ(x) à coefficients dans l’anneau ℤp des entiers p-adiques, soit un facteur propre de ce polynôme, soit, dans le cas où Φ(x) est irréductible, un élément générateur de l’anneau des entiers de ℚp[x]/Φ(x)ℚp[x]. Cet algorithme se fonde sur l’algorithme Round Four pour le calcul de l’ordre maximal. Les expérimentations montrent que le nouvel algorithme est cependant beaucoup plus performant que l’algorithme Round Four.

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.

@article{JTNB_2002__14_1_151_0,
     author = {Ford, David and Pauli, Sebastian and Roblot, Xavier-Fran\c{c}ois},
     title = {A fast algorithm for polynomial factorization over $\mathbb {Q}_p$},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {151--169},
     publisher = {Universit\'e Bordeaux I},
     volume = {14},
     number = {1},
     year = {2002},
     mrnumber = {1925995},
     zbl = {1032.11053},
     language = {en},
     url = {https://www.numdam.org/item/JTNB_2002__14_1_151_0/}
}
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
SP  - 151
EP  - 169
VL  - 14
IS  - 1
PB  - Université Bordeaux I
UR  - https://www.numdam.org/item/JTNB_2002__14_1_151_0/
LA  - en
ID  - JTNB_2002__14_1_151_0
ER  - 
%0 Journal Article
%A Ford, David
%A Pauli, Sebastian
%A Roblot, Xavier-François
%T A fast algorithm for polynomial factorization over $\mathbb {Q}_p$
%J Journal de théorie des nombres de Bordeaux
%D 2002
%P 151-169
%V 14
%N 1
%I Université Bordeaux I
%U https://www.numdam.org/item/JTNB_2002__14_1_151_0/
%G en
%F JTNB_2002__14_1_151_0
Ford, David; Pauli, Sebastian; Roblot, Xavier-François. A fast algorithm for polynomial factorization over $\mathbb {Q}_p$. Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 1, pp. 151-169. https://www.numdam.org/item/JTNB_2002__14_1_151_0/

[1] A. Ash, R. Pinch, R. Taylor, An Â4 extension of Q attached to a non-selfdual automorphic form on GL(3). Math. Annalen 291 (1991), 753-766. | MR | Zbl

[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] H. Cohen, Personal communication, 1996.

[4] D. Ford, P. Letard, Implementing the Round Four maximal order algorithm. J. Théor. Nombres Bordeaux 6 (1994) 39-80, http://almira.math.u-bordeaux.fr:80/jtnb/1994-1/jtnb6-1.html. | Numdam | MR | Zbl

[5] E. Hallouin Calcul de fermeture intégrale en dimension 1 et factorisation. Thèse, Université de Poitiers, 1998.

[6] W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers (second edition). Springer-Verlag, Berlin, 1990. | MR | Zbl

[7] S. Pauli, Factoring Polynomials over Local Fields. Journal of Symbolic Computation, accepted 2001. | MR | Zbl

[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é Bordeaux I, 1997, http://www.desargues.univ-lyon1.fr/home/roblot/papers.htm#1.

[9] E. Weiss, Algebraic number theory. McGraw-Hill, 1963. | MR | Zbl