We present an algorithm that returns a proper factor of a polynomial over the -adic integers (if is reducible over ) or returns a power basis of the ring of integers of (if is irreducible over ). 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.
Dans cet article, nous présentons un algorithme qui retourne pour un polynôme à coefficients dans l’anneau des entiers -adiques, soit un facteur propre de ce polynôme, soit, dans le cas où est irréductible, un élément générateur de l’anneau des entiers de . 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.
@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 = {http://archive.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 - http://archive.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 http://archive.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, Volume 14 (2002) no. 1, pp. 151-169. http://archive.numdam.org/item/JTNB_2002__14_1_151_0/
[1] An Â4 extension of Q attached to a non-selfdual automorphic form on GL(3). Math. Annalen 291 (1991), 753-766. | MR | Zbl
, , ,[2] Zum Round 4 Algorithmus, Diplomarbeit, Technische Universität Berlin, 1996, http://www.math.TU-Berlin.DE/-kant/publications/diplom/baier.ps.gz.
,[3] Personal communication, 1996.
,[4] 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] Calcul de fermeture intégrale en dimension 1 et factorisation. Thèse, Université de Poitiers, 1998.
[6] Elementary and Analytic Theory of Algebraic Numbers (second edition). Springer-Verlag, Berlin, 1990. | MR | Zbl
,[7] Factoring Polynomials over Local Fields. Journal of Symbolic Computation, accepted 2001. | MR | Zbl
,[8] 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.
, ,