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},
     doi = {10.5802/jtnb.351},
     zbl = {1032.11053},
     mrnumber = {1925995},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.351/}
}
David Ford; Sebastian Pauli; Xavier-François Roblot. 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. doi : 10.5802/jtnb.351. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.351/

[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 1135542 | Zbl 0713.11036

[2] G. Baier, Zum Round 4 Algorithmus, Diplomarbeit, Technische Universität Berlin, 1996, .

[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, . | Numdam | MR 1305287 | Zbl 0817.11064

[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 1055830 | Zbl 0717.11045

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

[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, .

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