Nous démontrons une complexité polynomiale en temps pour l’algorithme de van Hoeij de factorisation de polynômes univariés à coefficients rationnels, ainsi que pour des variantes naturelles. En particulier, notre approche fournit aussi une complexité polynomiale pour les polynômes bivariés sur un corps fini.
We prove that van Hoeij’s original algorithm to factor univariate polynomials over the rationals runs in polynomial time, as well as natural variants. In particular, our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.
@article{JTNB_2009__21_1_15_0,
author = {Belabas, Karim and van Hoeij, Mark and Kl\"uners, J\"urgen and Steel, Allan},
title = {Factoring polynomials over global fields},
journal = {Journal de th\'eorie des nombres de Bordeaux},
pages = {15--39},
publisher = {Universit\'e Bordeaux 1},
volume = {21},
number = {1},
year = {2009},
doi = {10.5802/jtnb.655},
mrnumber = {2537701},
language = {en},
url = {http://archive.numdam.org/articles/10.5802/jtnb.655/}
}
TY - JOUR AU - Belabas, Karim AU - van Hoeij, Mark AU - Klüners, Jürgen AU - Steel, Allan TI - Factoring polynomials over global fields JO - Journal de théorie des nombres de Bordeaux PY - 2009 SP - 15 EP - 39 VL - 21 IS - 1 PB - Université Bordeaux 1 UR - http://archive.numdam.org/articles/10.5802/jtnb.655/ DO - 10.5802/jtnb.655 LA - en ID - JTNB_2009__21_1_15_0 ER -
%0 Journal Article %A Belabas, Karim %A van Hoeij, Mark %A Klüners, Jürgen %A Steel, Allan %T Factoring polynomials over global fields %J Journal de théorie des nombres de Bordeaux %D 2009 %P 15-39 %V 21 %N 1 %I Université Bordeaux 1 %U http://archive.numdam.org/articles/10.5802/jtnb.655/ %R 10.5802/jtnb.655 %G en %F JTNB_2009__21_1_15_0
Belabas, Karim; van Hoeij, Mark; Klüners, Jürgen; Steel, Allan. Factoring polynomials over global fields. Journal de théorie des nombres de Bordeaux, Tome 21 (2009) no. 1, pp. 15-39. doi : 10.5802/jtnb.655. http://archive.numdam.org/articles/10.5802/jtnb.655/
[Bel03] K. Belabas, A relative van Hoeij algorithm over number fields. Journal of Symbolic Computation 37 (2004), 641–668. | MR | Zbl
[BCP97] W. Bosma, J. Cannon, C. Playoust, The Magma Algebra System I: The User Language. Journal of Symbolic Computation 24 (3) (1997), 235–265. | MR | Zbl
[BLSSW04] A. Bostan, G. Lecerf, B. Salvy, É. Schost and B. Wiebelt, Complexity issues in bivariate polynomial factorization. Proceedings of ISSAC (2004). | MR | Zbl
[GvzG00] J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, New York, 1999. | MR | Zbl
[HJLS89] J. Håstad, B. Just, J. C. Lagarias and C.-P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18 (1989), 859–881. | MR | Zbl
[Hoe02] M. van Hoeij, Factoring polynomials and the knapsack problem. J. Number Theory 95 (2002), 167–189. | MR | Zbl
[Len82] A. K. Lenstra, Lattices and factorization of polynomials over algebraic number fields. Springer Lecture Notes in Computer Science 144 (1982), 32–39. | MR | Zbl
[LLL82] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), no. 4, 515–534. | MR | Zbl
[MPS99] M. Mignotte, L. Pasteur and D. Stefanescu, Polynomials: An Algorithmic Approach. Springer, 1999. | MR | Zbl
[Mah61] K. Mahler, On the zeros of the derivative of a polynomial. Proc. Roy. Soc. Ser. A 264 (1961), 145–154. | MR | Zbl
[Mil92] V. Miller, Factoring Polynomials via Relation-Finding. ISTCS ’92, Springer Lecture Notes in Computer Science 601 (1992), 115–121. | MR
[NS05] P. Nguyen and D. Stehlé, Floating point LLL revisited. Eurocrypt’05, Springer Lecture Notes in Computer Science 3494 (2005), 215–233. | MR | Zbl
[PZ89] M. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory. Cambridge University Press, 1989. | MR | Zbl
[PO06] M. E. Pohst, Factoring polynomials over global fields. I. Journal of Symbolic Computation 39 (2005), 617–630. | MR | Zbl
[PM06] M. E. Pohst and J. Méndez Omaña, Factoring polynomials over global fields. II. Journal of Symbolic Computation 40 (2005), 1325–1339. | MR | Zbl
[SSH93] T. Sasaki, M. Sasaki, A unified method for multivariate polynomial factorization. Japan J. Industrial and Applied Math 10 (1993), no. 1, 21–39. | MR | Zbl
[Sch84] A. Schönhage, Factorization of univariate integer polynomials by Diophantine approximation and an improved basis reduction algorithm. In Automata, languages and programming (Antwerp, 1984), Springer Lecture Notes in Computer Science 172 (1984), 436–447. | MR | Zbl
[Zas69] H. Zassenhaus, On Hensel factorization I. Journal of Number Theory 1 (1969), 291–311. | MR | Zbl
Cité par Sources :
