Factorisation des polynômes à plusieurs variables

Lecerf, Grégoire

Journées Nationales de Calcul Formel. 13 – 17 Mai 2013, Les cours du CIRM, no. 1 (2013), Exposé no. 2, 85 p.

[1] J. Abbott, V. Shoup et P. Zimmermann : Factorization in $\mathbb{Z}\left[x\right]$ : the searching phase. In ISSAC ’00 : Proceedings of the 2000 international symposium on Symbolic and algebraic computation, pages 1–7, New York, NY, USA, 2000. ACM Press. | DOI | Zbl

[2] F. K. Abu Salem : An efficient sparse adaptation of the polytope method over ${𝔽}_p$ and a record-high binary bivariate factorisation. J. Symbolic Comput., 43(5) :311–341, 2008. | DOI | Zbl

[3] F. K. Abu Salem, Shuhong Gao et A. G. B. Lauder : Factoring polynomials via polytopes. In ISSAC ’04 : Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, pages 4–11, New York, 2004. ACM Press. | DOI | Zbl

[4] M. Avendaño, T. Krick et M. Sombra : Factoring bivariate sparse (lacunary) polynomials. J. Complexity, 23(2) :193–216, 2007. | DOI | MR | Zbl

[5] C. Bajaj, J. Canny, T. Garrity et J. Warren : Factoring rational polynomials over the complex numbers. SIAM J. Comput., 22(2) :318–331, 1993. | DOI | MR | Zbl

[6] K. Belabas, M. van Hoeij, M., J. Klüners et A. Steel : Factoring polynomials over global fields. J. Théor. Nombres Bordeaux, 21(1) :15–39, 2009. | DOI | MR | Zbl

[7] E. R. Berlekamp : Factoring polynomials over finite fields. Bell System Tech. J., 46 :1853–1859, 1967. | DOI | MR

[8] E. R. Berlekamp : Factoring polynomials over large finite fields. Math. Comp., 24 :713–735, 1970. | DOI | MR

[9] L. Bernardin et M. B. Monagan : Efficient multivariate factorization over finite fields. In Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 1997), volume 1255 de Lecture Notes in Comput. Sci., pages 15–28. Springer-Verlag, 1997. | DOI

[10] J. Berthomieu, J. van der Hoeven et G. Lecerf : Relaxed algorithms for $p$-adic numbers. Journal de Théorie des Nombres de Bordeaux, 23(3) :541–577, 2011. | DOI | MR | Zbl

[11] J. Berthomieu et G. Lecerf : Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations. Math. Comp., 81(279) :1799–1821, 2012. | DOI | MR | Zbl

[12] D. A. Bini et G. Fiorentino : Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms, 23(2-3) :127–173, 2000. | DOI | Zbl

[13] P. B. Borwein : Computational Excursions in Analysis and Number Theory. CMS Books in Mathematics. Springer-Verlag, 2002. | DOI | Zbl

[14] A. Bostan : Algorithmes rapides pour les polynômes, séries formelles et matrices, volume 1 de Les cours du CIRM, pages 75–262. cedram.org, 2010. Disponible depuis . | DOI

[15] A. Bostan, G. Lecerf, B. Salvy, É. Schost et B. Wiebelt : Complexity issues in bivariate polynomial factorization. In ISSAC ’04 : Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 42–49. ACM Press, 2004. | DOI | Zbl

[16] P. Bürgisser, M. Clausen et M. A. Shokrollahi : Algebraic complexity theory. Springer-Verlag, 1997. | DOI | Zbl

[17] D. G. Cantor et H. Zassenhaus : A new algorithm for factoring polynomials over finite fields. Math. Comp., 36(154) :587–592, 1981. | DOI | MR | Zbl

[18] Jingwei Chen, D. Stehlé et G. Villard : A new view on HJLS and PSLQ : sums and projections of lattices. À paraître dans les actes de la conférence ISSAC’13, 2013. | DOI | Zbl

[19] G. Chèze : Absolute polynomial factorization in two variables and the knapsack problem. In ISSAC ’04 : Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 87–94. ACM Press, 2004. | DOI | Zbl

[20] G. Chèze : Des méthodes symboliques-numériques et exactes pour la factorisation absolue des polynômes en deux variables. Thèse de doctorat, Université de Nice-Sophia Antipolis (France), 2004.

[21] G. Chèze et A. Galligo : Four lectures on polynomial absolute factorization. In A. Dickenstein et I. Z. Emiris, éditeurs : Solving polynomial equations : foundations, algorithms, and applications, volume 14 de Algorithms Comput. Math., pages 339–392. Springer-Verlag, 2005. | DOI | Zbl

[22] G. Chèze et A. Galligo : From an approximate to an exact absolute polynomial factorization. J. Symbolic Comput., 41(6) :682–696, 2006. | DOI | MR | Zbl

[23] G. Chèze et G. Lecerf : Lifting and recombination techniques for absolute factorization. J. Complexity, 23(3) :380–420, 2007. | DOI | MR | Zbl

[24] D. Coppersmith et C. A. Neff : Roots of a polynomial and its derivatives. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), pages 271–279. ACM Press, 1994. | Zbl

[25] J. H. Davenport et B. M. Trager : Factorization over finitely generated fields. In SYMSAC’81 : Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, pages 200–205. ACM Press, 1981. | DOI

[26] W. Decker, G.-M. Greuel, G. Pfister et H. Schönemann : Singular 3-1-6 — A computer algebra system for polynomial computations, 2012. http://www.singular.uni-kl.de.

[27] I. Z. Emiris, B. Mourrain et E. P. Tsigaridas : Real algebraic numbers : Complexity analysis and experimentation. In P. Hertling, C. M. Hoffmann, W. Luther et N. Revol, éditeurs : Reliable Implementation of Real Number Algorithms : Theory and Practice, volume 5045 de Lecture Notes in Computer Science, pages 57–82. Springer Berlin Heidelberg, 2008. | DOI

[28] H. R. P. Ferguson, D. H. Bailey et S. Arno : Analysis of PSLQ, an integer relation finding algorithm. Math. Comp., 68 :351–369, 1999. | DOI | MR | Zbl

[29] Ph. Flajolet et J.-M. Steyaert : A branching process arising in dynamic hashing, trie searching and polynomial factorization. In M. Nielsen et E. Schmidt, éditeurs : Automata, Languages and Programming, volume 140 de Lecture Notes in Computer Science, pages 239–251. Springer Berlin Heidelberg, 1982. | DOI

[30] A. Fröhlich et J. C. Shepherdson : On the factorisation of polynomials in a finite number of steps. Math. Z., 62 :331–334, 1955. | DOI | MR | Zbl

[31] A. Fröhlich et J. C. Shepherdson : Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A., 248 :407–432, 1956. | DOI | MR | Zbl

[32] M. Fürer : Faster integer multiplication. In Proceedings of the Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007), pages 57–66. ACM Press, 2007. | DOI | Zbl

[33] M. Fürer : Faster integer multiplication. SIAM J. Comput., 39(3) :979–1005, 2009. | DOI | MR | Zbl

[34] Shuhong Gao : Absolute irreducibility of polynomials via Newton polytopes. J. Algebra, 237(2) :501–520, 2001. | DOI | MR | Zbl

[35] Shuhong Gao : Factoring multivariate polynomials via partial differential equations. Math. Comp., 72(242) :801–822, 2003. | DOI | MR | Zbl

[36] Shuhong Gao et A. G. B. Lauder : Hensel lifting and bivariate polynomial factorisation over finite fields. Math. Comp., 71(240) :1663–1676, 2002. | DOI | MR | Zbl

[37] Shuhong Gao et V. M. Rodrigues : Irreducibility of polynomials modulo $p$ via Newton polytopes. J. Number Theory, 101(1) :32–47, 2003. | DOI | MR | Zbl

[38] J. von zur Gathen et E. Kaltofen : Factoring sparse multivariate polynomials. J. Comput. System Sci., 31(2) :265–287, 1985. Special issue : Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). | DOI | Zbl

[39] J. von zur Gathen et E. Kaltofen : Factorization of multivariate polynomials over finite fields. Math. Comp., 45(171) :251–261, 1985. | DOI | MR | Zbl

[40] J. von zur Gathen : Factoring sparse multivariate polynomials. In 24th Annual IEEE Symposium on Foundations of Computer Science, pages 172–179, Los Alamitos, CA, USA, 1983. IEEE Computer Society. | DOI

[41] J. von zur Gathen : Hensel and Newton methods in valuation rings. Math. Comp., 42(166) :637–661, 1984. | DOI | MR | Zbl

[42] J. von zur Gathen : Irreducibility of multivariate polynomials. J. Comput. System Sci., 31(2) :225–264, 1985. Special issue : Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983). | DOI | MR | Zbl

[43] J. von zur Gathen : Who was who in polynomial factorization. In Proceedings of the 2006 international symposium on Symbolic and algebraic computation, pages 1–2, New York, NY, USA, 2006. ACM Press. | DOI

[44] J. von zur Gathen et J. Gerhard : Modern computer algebra. Cambridge University Press, New York, 2${}^e$ édition, 2003. | DOI | Zbl

[45] J. Gerhard : Fast modular algorithms for squarefree factorization and Hermite integration. Appl. Algebra Engrg. Comm. Comput., 11(3) :203–226, 2001. | DOI | MR | Zbl

[46] P. Gianni et B. Trager : Square-free algorithms in positive characteristic. Appl. Algebra Engrg. Comm. Comput., 7(1) :1–14, 1996. | DOI | MR | Zbl

[47] W. Hart, M. van Hoeij et A. Novocin : Practical polynomial factoring in polynomial time. In ISSAC ’11 : Proceedings of the 36th international symposium on Symbolic and algebraic computation, pages 163–170, New York, NY, USA, 2011. ACM Press. | DOI | Zbl

[48] J. Heintz et M. Sieveking : Absolute primality of polynomials is decidable in random polynomial time in the number of variables. In Automata, languages and programming (Akko, 1981), volume 115 de Lecture Notes in Comput. Sci., pages 16–28. Springer-Verlag, 1981. | DOI | Zbl

[49] P. Henrici : Applied and Computational Complex Analysis, Volume 1, Power Series Integration Conformal Mapping Location of Zero. Wiley Classics Library. Wiley, 1988. | Zbl

[50] G. Hermann : Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Math. Ann., 95(1) :736–788, 1926. | DOI | MR | Zbl

[51] D. Hilbert : Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten. J. Reine Angew. Math., 110, 1892. | DOI | Zbl

[52] M. van Hoeij : Factoring polynomials and the knapsack problem. J. Number Theory, 95(2) :167–189, 2002. | DOI | MR | Zbl

[53] J. van der Hoeven : New algorithms for relaxed multiplication. J. Symbolic Comput., 42(8) :792–802, 2007. | DOI | MR | Zbl

[54] J. van der Hoeven : Calcul analytique, volume 2 de Les cours du CIRM, pages 1–85. cedram.org, 2011. Cours no. IV, disponible depuis http://ccirm.cedram.org/item?id=CCIRM_2011__2_1_A4_0. | DOI

[55] J. van der Hoeven et G. Lecerf : On the bit-complexity of sparse polynomial and series multiplication. J. Symbolic Comput., 50 :227–254, 2013. | DOI | MR | Zbl

[56] J. van der Hoeven, G. Lecerf, B. Mourrain et al. : Mathemagix, 2002. http://www.mathemagix.org.

[57] J.-P. Jouanolou : Théorèmes de Bertini et applications, volume 42 de Progress in Mathematics. Birkhäuser Boston, 1983. | Zbl

[58] E. Kaltofen : Polynomial factorization. In B. Buchberger, G. Collins et R. Loos, éditeurs : Computer algebra, pages 95–113. Springer-Verlag, 1982.

[59] E. Kaltofen : A polynomial reduction from multivariate to bivariate integral polynomial factorization. In Proceedings of the 14th Symposium on Theory of Computing, pages 261–266. ACM Press, 1982. | DOI

[60] E. Kaltofen : Effective Hilbert irreducibility. Inform. and Control, 66(3) :123–137, 1985. | DOI | MR | Zbl

[61] E. Kaltofen : Fast parallel absolute irreducibility testing. J. Symbolic Comput., 1(1) :57–67, 1985. | DOI | MR | Zbl

[62] E. Kaltofen : Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput., 14(2) :469–489, 1985. | DOI | MR | Zbl

[63] E. Kaltofen : Sparse Hensel lifting. In Proceedings of EUROCAL ’85, Vol. 2 (Linz, 1985), volume 204 de Lecture Notes in Comput. Sci., pages 4–17. Springer-Verlag, 1985. | DOI | Zbl

[64] E. Kaltofen : Uniform closure properties of p-computable functions. In Proc. 18th Annual ACM Symp. Theory Comput., pages 330–337. ACM Press, 1986. Also published as part of [65] and [66]. | DOI

[65] E. Kaltofen : Greatest common divisors of polynomials given by straight-line programs. J. ACM, 35(1) :231–264, 1988. | DOI | MR | Zbl

[66] E. Kaltofen : Factorization of polynomials given by straight-line programs. In S. Micali, éditeur : Randomness and Computation, volume 5 de Advances in Computing Research, pages 375–412. JAI Press Inc., Greenwhich, Connecticut, 1989.

[67] E. Kaltofen : Polynomial factorization 1982–1986. In Computers in mathematics (Stanford, CA, 1986), volume 125 de Lecture Notes in Pure and Appl. Math., pages 285–309. Dekker, 1990. | MR | Zbl

[68] E. Kaltofen : Polynomial factorization 1987–1991. In LATIN ’92 (São Paulo, 1992), volume 583 de Lecture Notes in Comput. Sci., pages 294–313. Springer-Verlag, 1992. | DOI

[69] E. Kaltofen : Effective Noether irreducibility forms and applications. J. Comput. System Sci., 50(2) :274–295, 1995. | DOI | MR | Zbl

[70] E. Kaltofen : Polynomial factorization : a success story. In ISSAC ’03 : Proceedings of the 2003 international symposium on Symbolic and algebraic computation, pages 3–4. ACM Press, 2003. | DOI | Zbl

[71] E. Kaltofen et P. Koiran : On the complexity of factoring bivariate supersparse (lacunary) polynomials. In ISSAC ’05 : Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, pages 208–215, 2005. | DOI | Zbl

[72] E. Kaltofen et P. Koiran : Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields. In ISSAC ’06 : Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, pages 162–168, 2006. | DOI | Zbl

[73] E. Kaltofen et V. Shoup : Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67(223) :1179–1197, 1998. | DOI | MR | Zbl

[74] E. Kaltofen et B. Trager : Computing with polynomials given by black boxes for their evaluations : Greatest common divisors, factorization, separation of numerators and denominators. In Proc. 29th Annual Symp. Foundations of Comp. Sci., pages 296–305. IEEE, 1988. | DOI | MR | Zbl

[75] E. Kaltofen et B. Trager : Computing with polynomials given by black boxes for their evaluations : Greatest common divisors, factorization, separation of numerators and denominators. J. Symbolic Comput., 9(3) :301–320, 1990. | DOI | MR | Zbl

[76] R. Kannan, A. K. Lenstra et L. Lovász : Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, STOC ’84, pages 191–200, New York, NY, USA, 1984. ACM Press. | DOI | MR | Zbl

[77] K. S. Kedlaya et C. Umans : Fast modular composition in any characteristic. In 49th Annual IEEE Symposium on Foundations of Computer Science 2008 (FOCS ’08), pages 146–155, 2008. | DOI

[78] A. Kipnis et A. Shamir : Cryptanalysis of the HFE public key cryptosystem by relinearization. In M. J. Wiener, éditeur : Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 de Lecture Notes in Computer Science, pages 19–30. Springer-Verlag, 1999. | DOI | Zbl

[79] P. Kirrinnis : Partial fraction decomposition in $ℂ\left(z\right)$ and simultaneous Newton iteration for factorization in $ℂ\left[z\right]$. J. Complexity, 14(3) :378–444, 1998. | DOI | MR | Zbl

[80] S. C. Kleene : General recursive functions of natural numbers. Mathematische Annalen, 112 :727–742, 1936. | DOI | MR | Zbl

[81] S. L. Kleiman : Bertini and his two fundamental theorems. Rend. Circ. Mat. Palermo (2) Suppl., 55 :9–37, 1998. Studies in the history of modern mathematics, III. | Zbl

[82] D. E. Knuth : The Art of Computer Programming, Volume II : Seminumerical Algorithms. Addison Wesley Longman, 3${}^e$ édition, 1998. | Zbl

[83] L. Kronecker : Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. reine angew. Math., 92 :1–122, 1882. | DOI | Zbl

[84] S. Lang : Algebra, volume 211 de Graduate Texts in Mathematics. Springer-Verlag, 3${}^e$ édition, 2002. | DOI

[85] G. Lecerf : Sharp precision in Hensel lifting for bivariate polynomial factorization. Math. Comp., 75 :921–933, 2006. | DOI | MR | Zbl

[86] G. Lecerf : Improved dense multivariate polynomial factorization algorithms. J. Symbolic Comput., 42(4) :477–494, 2007. | DOI | MR | Zbl

[87] G. Lecerf : Fast separable factorization and applications. Appl. Alg. Eng. Comm. Comp., 19(2), 2008. | DOI | MR | Zbl

[88] G. Lecerf : New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. Appl. Alg. Eng. Comm. Comp., 21(2) :151–176, 2010. | DOI | MR | Zbl

[89] G. Lecerf et É. Schost : Fast multivariate power series multiplication in characteristic zero. SADIO Electronic Journal on Informatics and Operations Research, 5(1) :1–10, 2003. | Zbl

[90] A. K. Lenstra, H. W. Lenstra, Jr. et L. Lovász : Factoring polynomials with rational coefficients. Math. Ann., 261(4) :515–534, 1982. | DOI | MR | Zbl

[91] H. W. Lenstra, Jr. : Finding small degree factors of lacunary polynomials. In Kálmán G., Henryk I. et Jerzy U., éditeurs : Number Theory in Progress, volume 1 Diophantine Problems and Polynomials, pages 267–276. Stefan Banach Internat. Center, Walter de Gruyter Berlin/New York, 1999. Proc. Internat. Conf. Number Theory in Honor of the 60th Birthday of Andrzej Schinzel, Zakopane, Poland June 30–July 9, 1997. | DOI

[92] L. Leroux : Algorithmes pour les polynômes lacunaires. Thèse de doctorat, Université de Caen, 2011. http://tel.archives-ouvertes.fr/docs/00/58/06/56/PDF/these.pdf.

[93] M. Marden : Geometry of polynomials. Second edition. Mathematical Surveys, No. 3. American Mathematical Society, 1966. | Zbl

[94] M. Mignotte : An inequality about factors of polynomials. Math. Comp., 28 :1153–1157, 1974. | DOI | MR | Zbl

[95] R. Mines et F. Richman : Separability and factoring polynomials. Rocky Mountain J. Math., 12(1) :43–54, 1982. | DOI | MR | Zbl

[96] R. Mines, F. Richman et W. Ruitenburg : A course in constructive algebra. Universitext. Springer-Verlag, 1988. | DOI | MR | Zbl

[97] G. L. Mullen et D. Panario : Handbook of Finite Fields. Discrete Mathematics and Its Applications. Chapman and Hall/CRC, 2013. | DOI | Zbl

[98] D. Mumford : Algebraic geometry. I Complex projective varieties. Classics in Mathematics. Springer-Verlag, 1995. Reprint of the 1976 edition. | Zbl

[99] D. R. Musser : Algorithms for Polynomial Factorization. Thèse de doctorat, C.S. Department, Univ. of Wisconsin, 1971.

[100] D. R. Musser : Multivariate polynomial factorization. J. Assoc. Comput. Mach., 22 :291–308, 1975. | DOI | MR | Zbl

[101] A. Neff et J. H. Reif : An $O(n^{1+ϵ}logb)$ algorithm for the complex roots problem. In Proceedings of the 35th Annual IEEE Conference on Foundations of Computer Science (FOCS ’94), pages 540–547. IEEE Computer Society Press, 1994. | DOI

[102] C. A. Neff et J. H. Reif : An efficient algorithm for the complex roots problem. J. Complexity, 12(2) :81–115, 1996. | DOI | MR | Zbl

[103] Phong Q. Nguyen et B. Vallée, éditeurs. The LLL Algorithm. Survey and Applications. Information Security and Cryptography. Springer, 2010. | DOI | MR | Zbl

[104] H. Niederreiter : A new efficient factorization algorithm for polynomials over small finite fields. Appl. Algebra Engrg. Comm. Comput., 4(2) :81–87, 1993. | DOI | MR | Zbl

[105] H. Niederreiter : Factoring polynomials over finite fields using differential equations and normal bases. Math. Comp., 62(206) :819–830, 1994. | DOI | MR | Zbl

[106] A. Nijenhuis et H. Wilf : Combinatorial Algorithms for Computers and Calculators. Academic Press, 1978. | Zbl

[107] A. Novocin : Factoring Univariate Polynomials over the Rationals. Thèse de doctorat, Department of Mathematics Florida State University Tallahassee, 2008.

[108] A. Novocin et M. van Hoeij : Factoring univariate polynomials over the rationals. ACM Commun. Comput. Algebra, 42(3) :157–157, 2009. | DOI

[109] A. Novocin, D. Stehlé et G. Villard : An LLL-reduction algorithm with quasi-linear time complexity : extended abstract. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC ’11, pages 403–412, New York, NY, USA, 2011. ACM Press. | DOI | Zbl

[110] A. M. Ostrowski : Über die Bedeutung der Theorie der konvexen Polyeder für die formale Algebra. Jahresber. Deutsch. Math.-Verein., 30(2) :98–99, 1921. Talk given at Der Deutsche Mathematikertag vom 18–24 September 1921 in Jena. | Zbl

[111] A. M. Ostrowski : On the significance of the theory of convex polyhedra for formal algebra. ACM SIGSAM Bull., 33(1) :5, 1999. Translated from [110]. | DOI

[112] V. Y. Pan : Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. In STOC ’95 : Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 741–750. ACM Press, 1995. | DOI | Zbl

[113] V. Y. Pan : Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31(12) :97–138, 1996. | DOI | MR | Zbl

[114] V. Y. Pan : Solving a polynomial equation : some history and recent progress. SIAM Rev., 39(2) :187–220, 1997. | DOI | MR | Zbl

[115] V. Y. Pan : Approximating complex polynomial zeros : modified Weyl’s quadtree construction and improved Newton’s iteration. J. Complexity, 16(1) :213–264, 2000. Real computation and complexity (Schloss Dagstuhl, 1998). | DOI | MR | Zbl

[116] V. Y. Pan : Univariate polynomials : nearly optimal algorithms for numerical factorization and root-finding. J. Symbolic Comput., 33(5) :701–733, 2002. | DOI | MR | Zbl

[117] The PARI Group, Bordeaux. PARI/GP, 2012. Software available from http://pari.math.u-bordeaux.fr.

[118] Ph. Saux Picart : The Schur-Cohn algorithm revisited. J. Symbolic Comput., 26(4) :387–408, 1998. | DOI | MR | Zbl

[119] D. A. Plaisted : New NP-hard and NP-complete polynomial and integer divisibility problems. Theoret. Comput. Sci., 13 :125–138, 1984. | DOI | MR | Zbl

[120] J. Renegar : On the worst-case arithmetic complexity of approximating zeros of polynomials. J. Complexity, 3(2) :90–113, 1987. | DOI | MR | Zbl

[121] F. Richman : Seidenberg’s condition $P$. In Constructive mathematics (Las Cruces, N.M., 1980), volume 873 de Lecture Notes in Math., pages 1–11. Springer-Verlag, 1981. | DOI

[122] W. M. Ruppert : Reduzibilität ebener Kurven. J. Reine Angew. Math., 369 :167–191, 1986. | DOI | Zbl

[123] W. M. Ruppert : Reducibility of polynomials $f(x,y)$ modulo $p$. J. Number Theory, 77(1) :62–70, 1999. | DOI | Zbl

[124] T. Sasaki, T. Saito et T. Hilano : Analysis of approximate factorization algorithm. I. Japan J. Indust. Appl. Math., 9(3) :351–368, 1992. | DOI | MR | Zbl

[125] T. Sasaki et M. Sasaki : A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10(1) :21–39, 1993. | DOI | MR | Zbl

[126] T. Sasaki, M. Suzuki, M. Kolář et M. Sasaki : Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math., 8(3) :357–375, 1991. | DOI | MR | Zbl

[127] A. Schinzel : Polynomials with special regard to reducibility, volume 77 de Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2000. | DOI | Zbl

[128] A. Schönhage : Schnelle Berechnung von Kettenbruchentwicklugen. Acta Inform., 1 :139–144, 1971. | DOI | Zbl

[129] A. Schönhage : The fundamental theorem of algebra in terms of computational complexity. Rapport technique, Preliminary Report of Mathematisches Institut der Universität Tübingen, Germany, 1982.

[130] J. T. Schwartz : Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4) :701–717, 1980. | DOI | MR | Zbl

[131] A. Seidenberg : Construction of the integral closure of a finite integral domain. Rend. Sem. Mat. Fis. Milano, 40 :100–120, 1970. | DOI | MR | Zbl

[132] A. Seidenberg : Constructions in algebra. Trans. Amer. Math. Soc., 197 :273–313, 1974. | DOI | MR | Zbl

[133] A. Seidenberg : Constructions in a polynomial ring over the ring of integers. Amer. J. Math., 100(4) :685–703, 1978. | DOI | MR | Zbl

[134] I. R. Shafarevich : Basic algebraic geometry. 1 Varieties in projective space. Springer-Verlag, 2${}^e$ édition, 1994. | Zbl

[135] V. Shoup : NTL : A library for doing number theory. http ://www.shoup.net.

[136] A. Steel : Conquering inseparability : primary decomposition and multivariate factorization over algebraic function fields of positive characteristic. J. Symbolic Comput., 40(3) :1053–1075, 2005. | DOI | MR | Zbl

[137] W. A. Stein et al. : Sage Mathematics Software. The Sage Development Team, 2004. http ://www.sagemath.org.

[138] J. Stern : Fondements mathématiques de l’informatique. Ediscience international, 1994.

[139] A. Storjohann : Algorithms for matrix canonical forms. Thèse de doctorat, ETH, Zürich, Switzerland, 2000.

[140] B. M. Trager : Algebraic factoring and rational function integration. In Proceedings of the third ACM symposium on symbolic and algebraic computation, pages 219–226. ACM Press, 1976. | DOI | Zbl

[141] B. M. Trager : Integration of algebraic functions. Thèse de doctorat, M.I.T. (USA), 1984.

[142] E. P. Tsigaridas et I. Z. Emiris : On the complexity of real root isolation using continued fractions. Theoretical Computer Science, 392(1–3) :158–173, 2008. | DOI | MR | Zbl

[143] B. L. van der Waerden : Eine Bemerkung über die Unzerlegbarkeit von Polynomen. Math. Ann., 102(1) :738–739, 1930. | DOI | Zbl

[144] B. L. van der Waerden : Modern Algebra. Vol. I. Frederick Ungar Publishing Co., New York, N. Y., 1949. | Zbl

[145] P. S. Wang : An improved multivariate polynomial factoring algorithm. Math. Comp., 32(144) :1215–1231, 1978. | DOI | MR | Zbl

[146] P. S. Wang et L. P. Rothschild : Factoring multivariate polynomials over the integers. Math. Comp., 29 :935–950, 1975. | DOI | MR | Zbl

[147] M. Weimann : A lifting and recombination algorithm for rational factorization of sparse polynomials. J. Complexity, 26(6) :608–628, 2010. | DOI | MR | Zbl

[148] M. Weimann : Algebraic osculation and application to factorization of sparse polynomials. Found. Comput. Math., 12(2) :173–201, 2012. | DOI | MR | Zbl

[149] J.-C. Yakoubsohn : Finding zeros of analytic functions : $\alpha$ theory for secant type methods. J. Complexity, 15(2) :239–281, 1999. | DOI | MR

[150] J.-C. Yakoubsohn : Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions. J. Complexity, 21(5) :652–690, 2005. | DOI | MR | Zbl

[151] H. Zassenhaus : On Hensel factorization I. J. Number Theory, 1(1) :291–311, 1969. | DOI | MR | Zbl

[152] R. Zippel : Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM’ 79, numéro  72 de Lecture Notes in Computer Science, pages 216–226. Springer-Verlag, 1979. | DOI | Zbl

[153] R. Zippel : Probabilistic algorithms for sparse polynomials. In EUROSAM ’79 : Proceedings of the International Symposium on Symbolic and Algebraic Computation, numéro  72 de Lecture Notes in Comput. Sci., pages 216–226. Springer-Verlag, 1979. | DOI | Zbl

[154] R. Zippel : Newton’s iteration and the sparse Hensel algorithm (Extended Abstract). In SYMSAC ’81 : Proceedings of the fourth ACM Symposium on Symbolic and Algebraic Computation, pages 68–72, New York, 1981. ACM Press. | DOI

[155] R. Zippel : Effective Polynomial Computation. Kluwer Academic Publishers, 1993. | DOI | Zbl