Factoring polynomials over global fields
Karim Belabas1 ; Mark van Hoeij2 ; Jürgen Klüners3 ; Allan Steel4
1 Université Bordeaux 1 351 cours de la Libération F-33405 Talence, France
2 Florida State University Dept. of Mathematics Tallahassee, FL 32306, USA Supported by NSF grants 0098034, 0511544 and 0728853
3 Universität Paderborn Institut für Mathematik 33095 Paderborn, Germany
4 School of Mathematics and Statistics F07 University of Sydney NSW 2006, Australia
Journal de théorie des nombres de Bordeaux, Tome 21 (2009) no. 1, pp. 15-39.

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.

DOI : 10.5802/jtnb.655
Karim Belabas 1 ; Mark van Hoeij 2 ; Jürgen Klüners 3 ; Allan Steel 4

1 Université Bordeaux 1 351 cours de la Libération F-33405 Talence, France
2 Florida State University Dept. of Mathematics Tallahassee, FL 32306, USA Supported by NSF grants 0098034, 0511544 and 0728853
3 Universität Paderborn Institut für Mathematik 33095 Paderborn, Germany
4 School of Mathematics and Statistics F07 University of Sydney NSW 2006, Australia 
@article{JTNB_2009__21_1_15_0,
     author = {Karim Belabas and Mark van Hoeij and J\"urgen Kl\"uners and Allan Steel},
     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 = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.655/}
}
TY  - JOUR
AU  - Karim Belabas
AU  - Mark van Hoeij
AU  - Jürgen Klüners
AU  - Allan Steel
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  - https://jtnb.centre-mersenne.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 Karim Belabas
%A Mark van Hoeij
%A Jürgen Klüners
%A Allan Steel
%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 https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.655/
%R 10.5802/jtnb.655
%G en
%F JTNB_2009__21_1_15_0
Karim Belabas; Mark van Hoeij; Jürgen Klüners; Allan Steel. 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. https://jtnb.centre-mersenne.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 :