Factoring polynomials over global fields
Journal de Théorie des Nombres de Bordeaux, Volume 21 (2009) no. 1, pp. 15-39.

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.

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.

Published online:
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},
     zbl = {pre05620666},
     mrnumber = {2537701},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.655/}
}
TY  - JOUR
TI  - Factoring polynomials over global fields
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2009
DA  - 2009///
SP  - 15
EP  - 39
VL  - 21
IS  - 1
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.655/
UR  - https://zbmath.org/?q=an%3Apre05620666
UR  - https://www.ams.org/mathscinet-getitem?mr=2537701
UR  - https://doi.org/10.5802/jtnb.655
DO  - 10.5802/jtnb.655
LA  - en
ID  - JTNB_2009__21_1_15_0
ER  - 
%0 Journal Article
%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://doi.org/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, Volume 21 (2009) no. 1, pp. 15-39. doi : 10.5802/jtnb.655. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.655/

[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: 1484478 | Zbl: 0898.68039

[Bel03] K. Belabas, A relative van Hoeij algorithm over number fields. Journal of Symbolic Computation 37 (2004), 641–668. | MR: 2094619 | Zbl: 1137.11360

[BLSSW04] A. Bostan, G. Lecerf, B. Salvy, É. Schost and B. Wiebelt, Complexity issues in bivariate polynomial factorization. Proceedings of ISSAC (2004). | MR: 2126923 | Zbl: 1134.68595

[GvzG00] J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, New York, 1999. | MR: 1689167 | Zbl: 0936.11069

[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: 1015261 | Zbl: 0692.10033

[Hoe02] M. van Hoeij, Factoring polynomials and the knapsack problem. J. Number Theory 95 (2002), 167–189. | MR: 1924096 | Zbl: 1081.11080

[Len82] A. K. Lenstra, Lattices and factorization of polynomials over algebraic number fields. Springer Lecture Notes in Computer Science 144 (1982), 32–39. | MR: 700263 | Zbl: 0541.68018

[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: 682664 | Zbl: 0488.12001

[Mah61] K. Mahler, On the zeros of the derivative of a polynomial. Proc. Roy. Soc. Ser. A 264 (1961), 145–154. | MR: 133437 | Zbl: 0109.25005

[Mil92] V. Miller, Factoring Polynomials via Relation-Finding. ISTCS ’92, Springer Lecture Notes in Computer Science 601 (1992), 115–121. | MR: 1233832

[MPS99] M. Mignotte, L. Pasteur and D. Stefanescu, Polynomials: An Algorithmic Approach. Springer, 1999. | MR: 1690362 | Zbl: 0927.12004

[NS05] P. Nguyen and D. Stehlé, Floating point LLL revisited. Eurocrypt’05, Springer Lecture Notes in Computer Science 3494 (2005), 215–233. | MR: 2352190 | Zbl: 1137.94353

[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: 2178090 | Zbl: 1156.11347

[PO06] M. E. Pohst, Factoring polynomials over global fields. I. Journal of Symbolic Computation 39 (2005), 617–630. | MR: 2168610 | Zbl: 1156.11349

[PZ89] M. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory. Cambridge University Press, 1989. | MR: 1033013 | Zbl: 0685.12001

[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: 784270 | Zbl: 0569.68030

[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: 1208180 | Zbl: 0796.12006

[Zas69] H. Zassenhaus, On Hensel factorization I. Journal of Number Theory 1 (1969), 291–311. | MR: 242793 | Zbl: 0188.33703

Cited by Sources: