--- _id: '34889' abstract: - lang: eng text: 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. author: - first_name: Karim full_name: Belabas, Karim last_name: Belabas - first_name: Mark full_name: van Hoeij, Mark last_name: van Hoeij - first_name: Jürgen full_name: Klüners, Jürgen id: '21202' last_name: Klüners - first_name: Allan full_name: Steel, Allan last_name: Steel citation: ama: Belabas K, van Hoeij M, Klüners J, Steel A. Factoring polynomials over global fields. Journal de Théorie des Nombres de Bordeaux. 2009;21(1):15-39. doi:10.5802/jtnb.655 apa: Belabas, K., van Hoeij, M., Klüners, J., & Steel, A. (2009). Factoring polynomials over global fields. Journal de Théorie Des Nombres de Bordeaux, 21(1), 15–39. https://doi.org/10.5802/jtnb.655 bibtex: '@article{Belabas_van Hoeij_Klüners_Steel_2009, title={Factoring polynomials over global fields}, volume={21}, DOI={10.5802/jtnb.655}, number={1}, journal={Journal de Théorie des Nombres de Bordeaux}, publisher={Cellule MathDoc/CEDRAM}, author={Belabas, Karim and van Hoeij, Mark and Klüners, Jürgen and Steel, Allan}, year={2009}, pages={15–39} }' chicago: 'Belabas, Karim, Mark van Hoeij, Jürgen Klüners, and Allan Steel. “Factoring Polynomials over Global Fields.” Journal de Théorie Des Nombres de Bordeaux 21, no. 1 (2009): 15–39. https://doi.org/10.5802/jtnb.655.' ieee: 'K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, “Factoring polynomials over global fields,” Journal de Théorie des Nombres de Bordeaux, vol. 21, no. 1, pp. 15–39, 2009, doi: 10.5802/jtnb.655.' mla: Belabas, Karim, et al. “Factoring Polynomials over Global Fields.” Journal de Théorie Des Nombres de Bordeaux, vol. 21, no. 1, Cellule MathDoc/CEDRAM, 2009, pp. 15–39, doi:10.5802/jtnb.655. short: K. Belabas, M. van Hoeij, J. Klüners, A. Steel, Journal de Théorie Des Nombres de Bordeaux 21 (2009) 15–39. date_created: 2022-12-23T09:33:37Z date_updated: 2023-03-06T09:09:56Z department: - _id: '102' doi: 10.5802/jtnb.655 external_id: arxiv: - 'math/0409510 ' intvolume: ' 21' issue: '1' keyword: - Algebra and Number Theory language: - iso: eng page: 15-39 publication: Journal de Théorie des Nombres de Bordeaux publication_identifier: issn: - 1246-7405 publication_status: published publisher: Cellule MathDoc/CEDRAM status: public title: Factoring polynomials over global fields type: journal_article user_id: '93826' volume: 21 year: '2009' ...