staple
With cedram.org

Search the site

Table of contents for this issue | Previous article | Next article
Karim Belabas; Mark van Hoeij; Jürgen Klüners; Allan Steel
Factoring polynomials over global fields
Journal de théorie des nombres de Bordeaux, 21 no. 1 (2009), p. 15-39, doi: 10.5802/jtnb.655
Article PDF | Reviews MR 2537701 | Zbl pre05620666 | 1 citation in Cedram

Résumé - Abstract

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.

Bibliography

[Bel03] K. Belabas, A relative van Hoeij algorithm over number fields. Journal of Symbolic Computation 37 (2004), 641–668.  MR 2094619 |  Zbl 1137.11360
[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
[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
[MPS99] M. Mignotte, L. Pasteur and D. Stefanescu, Polynomials: An Algorithmic Approach. Springer, 1999.  MR 1690362 |  Zbl 0927.12004
[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
[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
[PZ89] M. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory. Cambridge University Press, 1989.  MR 1033013 |  Zbl 0685.12001
[PO06] M. E. Pohst, Factoring polynomials over global fields. I. Journal of Symbolic Computation 39 (2005), 617–630.  MR 2168610 |  Zbl 1156.11349
[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
[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
[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
[Zas69] H. Zassenhaus, On Hensel factorization I. Journal of Number Theory 1 (1969), 291–311.  MR 242793 |  Zbl 0188.33703