article published Karim Belabas author Mark van Hoeij author Jürgen Klüners author 21202 Allan Steel author 102 department 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. Cellule MathDoc/CEDRAM2009 eng Algebra and Number Theory 1246-7405 math/0409510 10.5802/jtnb.655 21115-39 K. Belabas, M. van Hoeij, J. Klüners, A. Steel, Journal de Théorie Des Nombres de Bordeaux 21 (2009) 15–39. Belabas, Karim, Mark van Hoeij, Jürgen Klüners, and Allan Steel. “Factoring Polynomials over Global Fields.” <i>Journal de Théorie Des Nombres de Bordeaux</i> 21, no. 1 (2009): 15–39. <a href="https://doi.org/10.5802/jtnb.655">https://doi.org/10.5802/jtnb.655</a>. K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, “Factoring polynomials over global fields,” <i>Journal de Théorie des Nombres de Bordeaux</i>, vol. 21, no. 1, pp. 15–39, 2009, doi: <a href="https://doi.org/10.5802/jtnb.655">10.5802/jtnb.655</a>. Belabas, K., van Hoeij, M., Klüners, J., &#38; Steel, A. (2009). Factoring polynomials over global fields. <i>Journal de Théorie Des Nombres de Bordeaux</i>, <i>21</i>(1), 15–39. <a href="https://doi.org/10.5802/jtnb.655">https://doi.org/10.5802/jtnb.655</a> @article{Belabas_van Hoeij_Klüners_Steel_2009, title={Factoring polynomials over global fields}, volume={21}, DOI={<a href="https://doi.org/10.5802/jtnb.655">10.5802/jtnb.655</a>}, 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} } Belabas K, van Hoeij M, Klüners J, Steel A. Factoring polynomials over global fields. <i>Journal de Théorie des Nombres de Bordeaux</i>. 2009;21(1):15-39. doi:<a href="https://doi.org/10.5802/jtnb.655">10.5802/jtnb.655</a> Belabas, Karim, et al. “Factoring Polynomials over Global Fields.” <i>Journal de Théorie Des Nombres de Bordeaux</i>, vol. 21, no. 1, Cellule MathDoc/CEDRAM, 2009, pp. 15–39, doi:<a href="https://doi.org/10.5802/jtnb.655">10.5802/jtnb.655</a>. 348892022-12-23T09:33:37Z2023-03-06T09:09:56Z