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.
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.
@article{JTNB_2009__21_1_15_0,
author = {Belabas, Karim and van Hoeij, Mark and Kl\"uners, J\"urgen and Steel, Allan},
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},
mrnumber = {2537701},
language = {en},
url = {https://www.numdam.org/articles/10.5802/jtnb.655/}
}
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 SP - 15 EP - 39 VL - 21 IS - 1 PB - Université Bordeaux 1 UR - https://www.numdam.org/articles/10.5802/jtnb.655/ DO - 10.5802/jtnb.655 LA - en ID - JTNB_2009__21_1_15_0 ER -
%0 Journal Article %A Belabas, Karim %A van Hoeij, Mark %A Klüners, Jürgen %A Steel, Allan %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://www.numdam.org/articles/10.5802/jtnb.655/ %R 10.5802/jtnb.655 %G en %F JTNB_2009__21_1_15_0
Belabas, Karim; van Hoeij, Mark; Klüners, Jürgen; Steel, Allan. Factoring polynomials over global fields. Journal de théorie des nombres de Bordeaux, Tome 21 (2009) no. 1, pp. 15-39. doi : 10.5802/jtnb.655. https://www.numdam.org/articles/10.5802/jtnb.655/
[Bel03] K. Belabas, A relative van Hoeij algorithm over number fields. Journal of Symbolic Computation 37 (2004), 641–668. | MR | Zbl
[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 | Zbl
[BLSSW04] A. Bostan, G. Lecerf, B. Salvy, É. Schost and B. Wiebelt, Complexity issues in bivariate polynomial factorization. Proceedings of ISSAC (2004). | MR | Zbl
[GvzG00] J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge University Press, New York, 1999. | MR | Zbl
[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 | Zbl
[Hoe02] M. van Hoeij, Factoring polynomials and the knapsack problem. J. Number Theory 95 (2002), 167–189. | MR | Zbl
[Len82] A. K. Lenstra, Lattices and factorization of polynomials over algebraic number fields. Springer Lecture Notes in Computer Science 144 (1982), 32–39. | MR | Zbl
[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 | Zbl
[MPS99] M. Mignotte, L. Pasteur and D. Stefanescu, Polynomials: An Algorithmic Approach. Springer, 1999. | MR | Zbl
[Mah61] K. Mahler, On the zeros of the derivative of a polynomial. Proc. Roy. Soc. Ser. A 264 (1961), 145–154. | MR | Zbl
[Mil92] V. Miller, Factoring Polynomials via Relation-Finding. ISTCS ’92, Springer Lecture Notes in Computer Science 601 (1992), 115–121. | MR
[NS05] P. Nguyen and D. Stehlé, Floating point LLL revisited. Eurocrypt’05, Springer Lecture Notes in Computer Science 3494 (2005), 215–233. | MR | Zbl
[PZ89] M. E. Pohst and H. Zassenhaus, Algorithmic algebraic number theory. Cambridge University Press, 1989. | MR | Zbl
[PO06] M. E. Pohst, Factoring polynomials over global fields. I. Journal of Symbolic Computation 39 (2005), 617–630. | MR | Zbl
[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 | Zbl
[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 | Zbl
[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 | Zbl
[Zas69] H. Zassenhaus, On Hensel factorization I. Journal of Number Theory 1 (1969), 291–311. | MR | Zbl
- Factoring sparse polynomials fast, Journal of Complexity, Volume 88 (2025), p. 101934 | DOI:10.1016/j.jco.2025.101934
- Factoring polynomials over function fields, Research in Number Theory, Volume 11 (2025) no. 1 | DOI:10.1007/s40993-024-00581-y
- Cryptanalysis of Rank-2 Module-LIP in Totally Real Number Fields, Advances in Cryptology – EUROCRYPT 2024, Volume 14657 (2024), p. 226 | DOI:10.1007/978-3-031-58754-2_9
- Improved computation of polynomial roots over number fields when using complex embeddings, Journal of Computational Algebra, Volume 12 (2024), p. 100026 | DOI:10.1016/j.jaca.2024.100026
- L’algorithmique de la théorie algébrique des nombres, Journées mathématiques X-UPS (2024), p. 89 | DOI:10.5802/xups.2005-02
- Computational Number Theory, Past, Present, and Future, Mathematics Going Forward, Volume 2313 (2023), p. 561 | DOI:10.1007/978-3-031-12244-6_38
- , Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (2023), p. 417 | DOI:10.1145/3597066.3597096
- Towards Faster Polynomial-Time Lattice Reduction, Advances in Cryptology – CRYPTO 2021, Volume 12826 (2021), p. 760 | DOI:10.1007/978-3-030-84245-1_26
- Intrinsic Complexity for Constructing Zero-Dimensional Gröbner Bases, Computer Algebra in Scientific Computing, Volume 12291 (2020), p. 245 | DOI:10.1007/978-3-030-60026-6_14
- Sparse bivariate polynomial factorization, Science China Mathematics, Volume 57 (2014) no. 10, p. 2123 | DOI:10.1007/s11425-014-4850-y
- Cryptography, Handbook of Finite Fields (2013), p. 777 | DOI:10.1201/b15006-22
- Generating subfields, Journal of Symbolic Computation, Volume 52 (2013), p. 17 | DOI:10.1016/j.jsc.2012.05.010
- , Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (2013), p. 13 | DOI:10.1145/2465506.2479779
- Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials, Algorithmica, Volume 63 (2012) no. 3, p. 616 | DOI:10.1007/s00453-011-9500-y
- Algebraic Osculation and Application to Factorization of Sparse Polynomials, Foundations of Computational Mathematics, Volume 12 (2012) no. 2, p. 173 | DOI:10.1007/s10208-012-9114-z
- Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, Journal of Complexity, Volume 27 (2011) no. 2, p. 246 | DOI:10.1016/j.jco.2010.10.004
- , Proceedings of the 36th international symposium on Symbolic and algebraic computation (2011), p. 163 | DOI:10.1145/1993886.1993914
- , Proceedings of the 36th international symposium on Symbolic and algebraic computation (2011), p. 345 | DOI:10.1145/1993886.1993937
- New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, Applicable Algebra in Engineering, Communication and Computing, Volume 21 (2010) no. 2, p. 151 | DOI:10.1007/s00200-010-0121-5
- Modular Las Vegas algorithms for polynomial absolute factorization, Journal of Symbolic Computation, Volume 45 (2010) no. 12, p. 1280 | DOI:10.1016/j.jsc.2010.06.010
- The van Hoeij Algorithm for Factoring Polynomials, The LLL Algorithm (2009), p. 283 | DOI:10.1007/978-3-642-02295-1_8
Cité par 21 documents. Sources : Crossref
