Factoring polynomials over global fields

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

Journal de Théorie des Nombres de Bordeaux (2009)

  • Volume: 21, Issue: 1, page 15-39
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Belabas, Karim, et al. "Factoring polynomials over global fields." Journal de Théorie des Nombres de Bordeaux 21.1 (2009): 15-39. <http://eudml.org/doc/10869>.

@article{Belabas2009,
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.},
affiliation = {Université Bordeaux 1 351 cours de la Libération F-33405 Talence, France; Florida State University Dept. of Mathematics Tallahassee, FL 32306, USA Supported by NSF grants 0098034, 0511544 and 0728853; Universität Paderborn Institut für Mathematik 33095 Paderborn, Germany; School of Mathematics and Statistics F07 University of Sydney NSW 2006, Australia},
author = {Belabas, Karim, van Hoeij, Mark, Klüners, Jürgen, Steel, Allan},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {global fields; factoring polynomials},
language = {eng},
number = {1},
pages = {15-39},
publisher = {Université Bordeaux 1},
title = {Factoring polynomials over global fields},
url = {http://eudml.org/doc/10869},
volume = {21},
year = {2009},
}

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
PB - Université Bordeaux 1
VL - 21
IS - 1
SP - 15
EP - 39
AB - 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.
LA - eng
KW - global fields; factoring polynomials
UR - http://eudml.org/doc/10869
ER -

References

top
  1. K. Belabas, A relative van Hoeij algorithm over number fields. Journal of Symbolic Computation 37 (2004), 641–668. Zbl1137.11360MR2094619
  2. W. Bosma, J. Cannon, C. Playoust, The Magma Algebra System I: The User Language. Journal of Symbolic Computation 24 (3) (1997), 235–265. Zbl0898.68039MR1484478
  3. A. Bostan, G. Lecerf, B. Salvy, É. Schost and B. Wiebelt, Complexity issues in bivariate polynomial factorization. Proceedings of ISSAC (2004). Zbl1134.68595MR2126923
  4. J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, New York, 1999. Zbl0936.11069MR1689167
  5. 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. Zbl0692.10033MR1015261
  6. M. van Hoeij, Factoring polynomials and the knapsack problem. J. Number Theory 95 (2002), 167–189. Zbl1081.11080MR1924096
  7. A. K. Lenstra, Lattices and factorization of polynomials over algebraic number fields. Springer Lecture Notes in Computer Science 144 (1982), 32–39. Zbl0541.68018MR700263
  8. A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), no. 4, 515–534. Zbl0488.12001MR682664
  9. M. Mignotte, L. Pasteur and D. Stefanescu, Polynomials: An Algorithmic Approach. Springer, 1999. Zbl0927.12004MR1690362
  10. K. Mahler, On the zeros of the derivative of a polynomial. Proc. Roy. Soc. Ser. A 264 (1961), 145–154. Zbl0109.25005MR133437
  11. V. Miller, Factoring Polynomials via Relation-Finding. ISTCS ’92, Springer Lecture Notes in Computer Science 601 (1992), 115–121. MR1233832
  12. P. Nguyen and D. Stehlé, Floating point LLL revisited. Eurocrypt’05, Springer Lecture Notes in Computer Science 3494 (2005), 215–233. Zbl1137.94353MR2352190
  13. M. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory. Cambridge University Press, 1989. Zbl0685.12001MR1033013
  14. M. E. Pohst, Factoring polynomials over global fields. I. Journal of Symbolic Computation 39 (2005), 617–630. Zbl1156.11349MR2168610
  15. M. E. Pohst and J. Méndez Omaña, Factoring polynomials over global fields. II. Journal of Symbolic Computation 40 (2005), 1325–1339. Zbl1156.11347MR2178090
  16. T. Sasaki, M. Sasaki, A unified method for multivariate polynomial factorization. Japan J. Industrial and Applied Math 10 (1993), no. 1, 21–39. Zbl0796.12006MR1208180
  17. 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. Zbl0569.68030MR784270
  18. H. Zassenhaus, On Hensel factorization I. Journal of Number Theory 1 (1969), 291–311. Zbl0188.33703MR242793

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.