Factorisation des polynômes à plusieurs variables

 Access to full text

 Full (PDF)

1. J. Abbott, V. Shoup et P. Zimmermann : Factorization in $\mathbb{Z}\left[x\right]$ : the searching phase. InISSAC ’00 : Proceedings of the 2000 international symposium on Symbolic and algebraic computation, pages 1–7, New York, NY, USA, 2000. ACM Press. Zbl1326.68339
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. Zbl1134.11045MR2406567
3. F. K. Abu Salem, Shuhong Gao et A. G. B. Lauder : Factoring polynomials via polytopes. InISSAC ’04 : Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, pages 4–11, New York, 2004. ACM Press. Zbl1088.68183MR2126918
4. M. Avendaño, T. Krick et M. Sombra : Factoring bivariate sparse (lacunary) polynomials. J. Complexity, 23(2) :193–216, 2007. Zbl1170.12004MR2314756
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. Zbl0772.12001MR1207788
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. Zbl1254.11116MR2537701
7. E. R. Berlekamp : Factoring polynomials over finite fields. Bell System Tech. J., 46 :1853–1859, 1967. Zbl0166.04901MR219231
8. E. R. Berlekamp : Factoring polynomials over large finite fields. Math. Comp., 24 :713–735, 1970. Zbl0247.12014MR276200
9. L. Bernardin et M. B. Monagan : Efficient multivariate factorization over finite fields. InApplied algebra, algebraic algorithms and error-correcting codes (Toulouse, 1997), volume 1255 de Lecture Notes in Comput. Sci., pages 15–28. Springer-Verlag, 1997. Zbl1039.68934MR1634102
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. Zbl1247.11152MR2861075
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. Zbl1271.12006MR2904603
12. D. A. Bini et G. Fiorentino : Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms, 23(2-3) :127–173, 2000. Zbl1018.65061MR1772050
13. P. B. Borwein : Computational Excursions in Analysis and Number Theory. CMS Books in Mathematics. Springer-Verlag, 2002. Zbl1020.12001MR1912495
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 http://dx.doi.org/10.5802/ccirm.9. 
15. A. Bostan, G. Lecerf, B. Salvy, É. Schost et B. Wiebelt : Complexity issues in bivariate polynomial factorization. InISSAC ’04 : Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 42–49. ACM Press, 2004. Zbl1134.68595MR2126923
16. P. Bürgisser, M. Clausen et M. A. Shokrollahi : Algebraic complexity theory. Springer-Verlag, 1997. Zbl1087.68568MR1440179
17. D. G. Cantor et H. Zassenhaus : A new algorithm for factoring polynomials over finite fields. Math. Comp., 36(154) :587–592, 1981. Zbl0493.12024MR606517
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. 
19. G. Chèze : Absolute polynomial factorization in two variables and the knapsack problem. InISSAC ’04 : Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 87–94. ACM Press, 2004. Zbl1134.68597MR2126929
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. InA. 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. Zbl1152.13302MR2161993
22. G. Chèze et A. Galligo : From an approximate to an exact absolute polynomial factorization. J. Symbolic Comput., 41(6) :682–696, 2006. Zbl1134.13022MR2208507
23. G. Chèze et G. Lecerf : Lifting and recombination techniques for absolute factorization. J. Complexity, 23(3) :380–420, 2007. Zbl1130.12007MR2330992
24. D. Coppersmith et C. A. Neff : Roots of a polynomial and its derivatives. InProceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), pages 271–279. ACM Press, 1994. Zbl0867.65022MR1285172
25. J. H. Davenport et B. M. Trager : Factorization over finitely generated fields. InSYMSAC’81 : Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, pages 200–205. ACM Press, 1981. Zbl0481.68040
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. Zbl0902.14040
27. I. Z. Emiris, B. Mourrain et E. P. Tsigaridas : Real algebraic numbers : Complexity analysis and experimentation. InP. 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. Zbl1165.65315
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. Zbl0927.11055MR1489971
29. Ph. Flajolet et J.-M. Steyaert : A branching process arising in dynamic hashing, trie searching and polynomial factorization. InM. Nielsen et E. Schmidt, éditeurs : Automata, Languages and Programming, volume 140 de Lecture Notes in Computer Science, pages 239–251. Springer Berlin Heidelberg, 1982. Zbl0482.68058MR675461
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. Zbl0064.24902MR71385
31. A. Fröhlich et J. C. Shepherdson : Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A., 248 :407–432, 1956. Zbl0070.03502MR74349
32. M. Fürer : Faster integer multiplication. InProceedings of the Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007), pages 57–66. ACM Press, 2007. Zbl1179.68198MR2402428
33. M. Fürer : Faster integer multiplication. SIAM J. Comput., 39(3) :979–1005, 2009. Zbl1192.68926MR2538847
34. Shuhong Gao : Absolute irreducibility of polynomials via Newton polytopes. J. Algebra, 237(2) :501–520, 2001. Zbl0997.12001MR1816701
35. Shuhong Gao : Factoring multivariate polynomials via partial differential equations. Math. Comp., 72(242) :801–822, 2003. Zbl1052.12006MR1954969
36. Shuhong Gao et A. G. B. Lauder : Hensel lifting and bivariate polynomial factorisation over finite fields. Math. Comp., 71(240) :1663–1676, 2002. Zbl1076.11064MR1933049
37. Shuhong Gao et V. M. Rodrigues : Irreducibility of polynomials modulo $p$ via Newton polytopes. J. Number Theory, 101(1) :32–47, 2003. Zbl1108.13307MR1979651
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). Zbl0599.68037MR828524
39. J. von zur Gathen et E. Kaltofen : Factorization of multivariate polynomials over finite fields. Math. Comp., 45(171) :251–261, 1985. Zbl0596.12017MR790658
40. J. von zur Gathen : Factoring sparse multivariate polynomials. In24th Annual IEEE Symposium on Foundations of Computer Science, pages 172–179, Los Alamitos, CA, USA, 1983. IEEE Computer Society. 
41. J. von zur Gathen : Hensel and Newton methods in valuation rings. Math. Comp., 42(166) :637–661, 1984. Zbl0581.13001MR736459
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). Zbl0604.68043MR828523
43. J. von zur Gathen : Who was who in polynomial factorization. InProceedings of the 2006 international symposium on Symbolic and algebraic computation, pages 1–2, New York, NY, USA, 2006. ACM Press. Zbl1236.68304MR1086727
44. J. von zur Gathen et J. Gerhard : Modern computer algebra. Cambridge University Press, New York, 2${}^e$ édition, 2003. Zbl1055.68168MR2001757
45. J. Gerhard : Fast modular algorithms for squarefree factorization and Hermite integration. Appl. Algebra Engrg. Comm. Comput., 11(3) :203–226, 2001. Zbl0987.11078MR1815131
46. P. Gianni et B. Trager : Square-free algorithms in positive characteristic. Appl. Algebra Engrg. Comm. Comput., 7(1) :1–14, 1996. Zbl0874.12009MR1464533
47. W. Hart, M. van Hoeij et A. Novocin : Practical polynomial factoring in polynomial time. InISSAC ’11 : Proceedings of the 36th international symposium on Symbolic and algebraic computation, pages 163–170, New York, NY, USA, 2011. ACM Press. Zbl1323.68603MR2895208
48. J. Heintz et M. Sieveking : Absolute primality of polynomials is decidable in random polynomial time in the number of variables. InAutomata, languages and programming (Akko, 1981), volume 115 de Lecture Notes in Comput. Sci., pages 16–28. Springer-Verlag, 1981. Zbl0462.68025MR635127
49. P. Henrici : Applied and Computational Complex Analysis, Volume 1, Power Series Integration Conformal Mapping Location of Zero. Wiley Classics Library. Wiley, 1988. Zbl0635.30001MR1008928
50. G. Hermann : Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Math. Ann., 95(1) :736–788, 1926. Zbl52.0127.01MR1512302
51. D. Hilbert : Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten. J. Reine Angew. Math., 110, 1892. Zbl24.0087.03
52. M. van Hoeij : Factoring polynomials and the knapsack problem. J. Number Theory, 95(2) :167–189, 2002. Zbl1081.11080MR1924096
53. J. van der Hoeven : New algorithms for relaxed multiplication. J. Symbolic Comput., 42(8) :792–802, 2007. Zbl1130.68103MR2345837
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. 
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. Zbl1261.65017MR2996877
56. J. van der Hoeven, G. Lecerf, B. Mourrainet 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. Zbl0519.14002MR725671
58. E. Kaltofen : Polynomial factorization. InB. Buchberger, G. Collins et R. Loos, éditeurs : Computer algebra, pages 95–113. Springer-Verlag, 1982. Zbl0519.68059
59. E. Kaltofen : A polynomial reduction from multivariate to bivariate integral polynomial factorization. InProceedings of the 14th Symposium on Theory of Computing, pages 261–266. ACM Press, 1982. 
60. E. Kaltofen : Effective Hilbert irreducibility. Inform. and Control, 66(3) :123–137, 1985. Zbl0584.12019MR824125
61. E. Kaltofen : Fast parallel absolute irreducibility testing. J. Symbolic Comput., 1(1) :57–67, 1985. Zbl0599.68038MR810135
62. E. Kaltofen : Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput., 14(2) :469–489, 1985. Zbl0605.12001MR784750
63. E. Kaltofen : Sparse Hensel lifting. InProceedings of EUROCAL ’85, Vol. 2 (Linz, 1985), volume 204 de Lecture Notes in Comput. Sci., pages 4–17. Springer-Verlag, 1985. Zbl0605.12011MR826553
64. E. Kaltofen : Uniform closure properties of p-computable functions. InProc. 18th Annual ACM Symp. Theory Comput., pages 330–337. ACM Press, 1986. Also published as part of [65] and [66]. 
65. E. Kaltofen : Greatest common divisors of polynomials given by straight-line programs. J. ACM, 35(1) :231–264, 1988. Zbl0642.68058MR926181
66. E. Kaltofen : Factorization of polynomials given by straight-line programs. InS. Micali, éditeur : Randomness and Computation, volume 5 de Advances in Computing Research, pages 375–412. JAI Press Inc., Greenwhich, Connecticut, 1989. Zbl0519.68059
67. E. Kaltofen : Polynomial factorization 1982–1986. InComputers in mathematics (Stanford, CA, 1986), volume 125 de Lecture Notes in Pure and Appl. Math., pages 285–309. Dekker, 1990. Zbl0773.11078MR1068540
68. E. Kaltofen : Polynomial factorization 1987–1991. InLATIN ’92 (São Paulo, 1992), volume 583 de Lecture Notes in Comput. Sci., pages 294–313. Springer-Verlag, 1992. Zbl0773.11078MR1253363
69. E. Kaltofen : Effective Noether irreducibility forms and applications. J. Comput. System Sci., 50(2) :274–295, 1995. Zbl0844.12006MR1330258
70. E. Kaltofen : Polynomial factorization : a success story. InISSAC ’03 : Proceedings of the 2003 international symposium on Symbolic and algebraic computation, pages 3–4. ACM Press, 2003. Zbl1068.68709
71. E. Kaltofen et P. Koiran : On the complexity of factoring bivariate supersparse (lacunary) polynomials. InISSAC ’05 : Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, pages 208–215, 2005. Zbl06459450MR2280549
72. E. Kaltofen et P. Koiran : Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields. InISSAC ’06 : Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, pages 162–168, 2006. MR2289115
73. E. Kaltofen et V. Shoup : Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67(223) :1179–1197, 1998. Zbl0902.11053MR1459389
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. InProc. 29th Annual Symp. Foundations of Comp. Sci., pages 296–305. IEEE, 1988. Zbl0712.12001
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. Zbl0712.12001MR1056629
76. R. Kannan, A. K. Lenstra et L. Lovász : Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. InProceedings of the sixteenth annual ACM symposium on Theory of computing, STOC ’84, pages 191–200, New York, NY, USA, 1984. ACM Press. 
77. K. S. Kedlaya et C. Umans : Fast modular composition in any characteristic. In49th Annual IEEE Symposium on Foundations of Computer Science 2008 (FOCS ’08), pages 146–155, 2008. 
78. A. Kipnis et A. Shamir : Cryptanalysis of the HFE public key cryptosystem by relinearization. InM. 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. Zbl0940.94012MR1729291
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. Zbl0934.12005MR1646107
80. S. C. Kleene : General recursive functions of natural numbers. Mathematische Annalen, 112 :727–742, 1936. Zbl0014.19402MR1513071
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. Zbl0926.14001MR1661859
82. D. E. Knuth : The Art of Computer Programming, Volume II : Seminumerical Algorithms. Addison Wesley Longman, 3${}^e$ édition, 1998. Zbl0895.68054MR378456
83. L. Kronecker : Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. reine angew. Math., 92 :1–122, 1882. Zbl14.0038.02
84. S. Lang : Algebra, volume 211 de Graduate Texts in Mathematics. Springer-Verlag, 3${}^e$ édition, 2002. Zbl0984.00001MR1878556
85. G. Lecerf : Sharp precision in Hensel lifting for bivariate polynomial factorization. Math. Comp., 75 :921–933, 2006. Zbl1125.12003MR2197000
86. G. Lecerf : Improved dense multivariate polynomial factorization algorithms. J. Symbolic Comput., 42(4) :477–494, 2007. Zbl1127.13021MR2317560
87. G. Lecerf : Fast separable factorization and applications. Appl. Alg. Eng. Comm. Comp., 19(2), 2008. Zbl1205.12008MR2389971
88. G. Lecerf : New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. Appl. Alg. Eng. Comm. Comp., 21(2) :151–176, 2010. Zbl1245.12008MR2600710
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. Zbl1209.68618
90. A. K. Lenstra, H. W. Lenstra, Jr. et L. Lovász : Factoring polynomials with rational coefficients. Math. Ann., 261(4) :515–534, 1982. Zbl0488.12001MR682664
91. H. W. Lenstra, Jr. : Finding small degree factors of lacunary polynomials. InKá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. Zbl0949.11053MR1689509
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. Zbl0162.37101MR225972
94. M. Mignotte : An inequality about factors of polynomials. Math. Comp., 28 :1153–1157, 1974. Zbl0299.12101MR354624
95. R. Mines et F. Richman : Separability and factoring polynomials. Rocky Mountain J. Math., 12(1) :43–54, 1982. Zbl0499.12019MR649738
96. R. Mines, F. Richman et W. Ruitenburg : A course in constructive algebra. Universitext. Springer-Verlag, 1988. Zbl0725.03044MR919949
97. G. L. Mullen et D. Panario : Handbook of Finite Fields. Discrete Mathematics and Its Applications. Chapman and Hall/CRC, 2013. Zbl1319.11001
98. D. Mumford : Algebraic geometry. I Complex projective varieties. Classics in Mathematics. Springer-Verlag, 1995. Reprint of the 1976 edition. Zbl0821.14001MR1344216
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. Zbl0301.65029MR396470
101. A. Neff et J. H. Reif : An $O(n^{1+ϵ}logb)$ algorithm for the complex roots problem. InProceedings of the 35th Annual IEEE Conference on Foundations of Computer Science (FOCS ’94), pages 540–547. IEEE Computer Society Press, 1994. 
102. C. A. Neff et J. H. Reif : An efficient algorithm for the complex roots problem. J. Complexity, 12(2) :81–115, 1996. Zbl0888.12005MR1398320
103. Phong Q. Nguyen et B. Vallée, éditeurs. The LLL Algorithm. Survey and Applications. Information Security and Cryptography. Springer, 2010. Zbl1179.11003MR2722178
104. H. Niederreiter : A new efficient factorization algorithm for polynomials over small finite fields. Appl. Algebra Engrg. Comm. Comput., 4(2) :81–87, 1993. Zbl0776.11070MR1223850
105. H. Niederreiter : Factoring polynomials over finite fields using differential equations and normal bases. Math. Comp., 62(206) :819–830, 1994. Zbl0797.11092MR1216262
106. A. Nijenhuis et H. Wilf : Combinatorial Algorithms for Computers and Calculators. Academic Press, 1978. Zbl0476.68047MR510047
107. A. Novocin : Factoring Univariate Polynomials over the Rationals. Thèse de doctorat, Department of Mathematics Florida State University Tallahassee, 2008. MR2711958
108. A. Novocin et M. van Hoeij : Factoring univariate polynomials over the rationals. ACM Commun. Comput. Algebra, 42(3) :157–157, 2009. 
109. A. Novocin, D. Stehlé et G. Villard : An LLL-reduction algorithm with quasi-linear time complexity : extended abstract. InProceedings of the 43rd annual ACM symposium on Theory of computing, STOC ’11, pages 403–412, New York, NY, USA, 2011. ACM Press. Zbl1288.68294MR2931990
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. Zbl48.0106.01
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]. 
112. V. Y. Pan : Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros. InSTOC ’95 : Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 741–750. ACM Press, 1995. Zbl0942.68796
113. V. Y. Pan : Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31(12) :97–138, 1996. Zbl0859.65045MR1418708
114. V. Y. Pan : Solving a polynomial equation : some history and recent progress. SIAM Rev., 39(2) :187–220, 1997. Zbl0873.65050MR1453318
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). Zbl1041.65043MR1762403
116. V. Y. Pan : Univariate polynomials : nearly optimal algorithms for numerical factorization and root-finding. J. Symbolic Comput., 33(5) :701–733, 2002. Zbl1004.65061MR1919911
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. Zbl0912.68066MR1646666
119. D. A. Plaisted : New NP-hard and NP-complete polynomial and integer divisibility problems. Theoret. Comput. Sci., 13 :125–138, 1984. Zbl0572.68027MR752098
120. J. Renegar : On the worst-case arithmetic complexity of approximating zeros of polynomials. J. Complexity, 3(2) :90–113, 1987. Zbl0642.65031MR907192
121. F. Richman : Seidenberg’s condition $P$. InConstructive mathematics (Las Cruces, N.M., 1980), volume 873 de Lecture Notes in Math., pages 1–11. Springer-Verlag, 1981. Zbl0461.03016MR644490
122. W. M. Ruppert : Reduzibilität ebener Kurven. J. Reine Angew. Math., 369 :167–191, 1986. Zbl0584.14012MR850633
123. W. M. Ruppert : Reducibility of polynomials $f(x,y)$ modulo $p$. J. Number Theory, 77(1) :62–70, 1999. Zbl0931.11005MR1695700
124. T. Sasaki, T. Saito et T. Hilano : Analysis of approximate factorization algorithm. I. Japan J. Indust. Appl. Math., 9(3) :351–368, 1992. Zbl0808.12001MR1189944
125. T. Sasaki et M. Sasaki : A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10(1) :21–39, 1993. Zbl0796.12006MR1208180
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. Zbl0757.12006MR1137647
127. A. Schinzel : Polynomials with special regard to reducibility, volume 77 de Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2000. Zbl0956.12001MR1770638
128. A. Schönhage : Schnelle Berechnung von Kettenbruchentwicklugen. Acta Inform., 1 :139–144, 1971. Zbl0223.68008
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. Zbl0452.68050MR594695
131. A. Seidenberg : Construction of the integral closure of a finite integral domain. Rend. Sem. Mat. Fis. Milano, 40 :100–120, 1970. Zbl0218.14023MR294327
132. A. Seidenberg : Constructions in algebra. Trans. Amer. Math. Soc., 197 :273–313, 1974. Zbl0356.13007MR349648
133. A. Seidenberg : Constructions in a polynomial ring over the ring of integers. Amer. J. Math., 100(4) :685–703, 1978. Zbl0416.13013MR509069
134. I. R. Shafarevich : Basic algebraic geometry. 1 Varieties in projective space. Springer-Verlag, 2${}^e$ édition, 1994. Zbl0362.14001MR1328833
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. Zbl1120.13026MR2167699
137. W. A. Steinet 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. InProceedings of the third ACM symposium on symbolic and algebraic computation, pages 219–226. ACM Press, 1976. Zbl0498.12005
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. Zbl1134.68067MR2394991
143. B. L. van der Waerden : Eine Bemerkung über die Unzerlegbarkeit von Polynomen. Math. Ann., 102(1) :738–739, 1930. Zbl56.0825.05MR1512605
144. B. L. van der Waerden : Modern Algebra. Vol. I. Frederick Ungar Publishing Co., New York, N. Y., 1949. Zbl0039.00902MR29363
145. P. S. Wang : An improved multivariate polynomial factoring algorithm. Math. Comp., 32(144) :1215–1231, 1978. Zbl0388.10035MR568284
146. P. S. Wang et L. P. Rothschild : Factoring multivariate polynomials over the integers. Math. Comp., 29 :935–950, 1975. Zbl0311.10052MR396471
147. M. Weimann : A lifting and recombination algorithm for rational factorization of sparse polynomials. J. Complexity, 26(6) :608–628, 2010. Zbl1236.12001MR2735422
148. M. Weimann : Algebraic osculation and application to factorization of sparse polynomials. Found. Comput. Math., 12(2) :173–201, 2012. Zbl1252.14007MR2898781
149. J.-C. Yakoubsohn : Finding zeros of analytic functions : $\alpha$ theory for secant type methods. J. Complexity, 15(2) :239–281, 1999. Zbl0944.65061MR1693876
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. Zbl1084.65055MR2170867
151. H. Zassenhaus : On Hensel factorization I. J. Number Theory, 1(1) :291–311, 1969. Zbl0188.33703MR242793
152. R. Zippel : Probabilistic algorithms for sparse polynomials. InProceedings EUROSAM’ 79, numéro  72 de Lecture Notes in Computer Science, pages 216–226. Springer-Verlag, 1979. Zbl0418.68040MR575692
153. R. Zippel : Probabilistic algorithms for sparse polynomials. InEUROSAM ’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. Zbl0418.68040MR575692
154. R. Zippel : Newton’s iteration and the sparse Hensel algorithm (Extended Abstract). InSYMSAC ’81 : Proceedings of the fourth ACM Symposium on Symbolic and Algebraic Computation, pages 68–72, New York, 1981. ACM Press. Zbl0482.68037
155. R. Zippel : Effective Polynomial Computation. Kluwer Academic Publishers, 1993. Zbl0794.11048