Centre de diffusion de revues académiques mathématiques

 
 
 
 

Les cours du CIRM

Table des matières de ce fascicule | Article précédent | Article suivant
Grégoire Lecerf
Factorisation des polynômes à plusieurs variables
Les cours du CIRM, 3 no. 1: Journées Nationales de Calcul Formel (2013), Exp. No. 2, 85 p., doi: 10.5802/ccirm.18
Article PDF

Bibliographie

[1] J. Abbott, V. Shoup et P. Zimmermann : Factorization in $\mathbb{Z}[x]$ : 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.
[2] F. K. Abu Salem : An efficient sparse adaptation of the polytope method over $\mathbb{F}_p$ and a record-high binary bivariate factorisation. J. Symbolic Comput., 43(5) :311–341, 2008.  MR 2406567 |  Zbl 1134.11045
[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.  MR 2126918 |  Zbl 1088.68183
[4] M. Avendaño, T. Krick et M. Sombra : Factoring bivariate sparse (lacunary) polynomials. J. Complexity, 23(2) :193–216, 2007.  MR 2314756 |  Zbl 1170.12004
[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.  MR 1207788 |  Zbl 0772.12001
[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. Cedram |  MR 2537701 |  Zbl 1254.11116
[7] E. R. Berlekamp : Factoring polynomials over finite fields. Bell System Tech. J., 46 :1853–1859, 1967.  MR 219231 |  Zbl 0166.04901
[8] E. R. Berlekamp : Factoring polynomials over large finite fields. Math. Comp., 24 :713–735, 1970.  MR 276200 |  Zbl 0247.12014
[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.  MR 1634102 |  Zbl 1039.68934
[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. Cedram |  MR 2861075 |  Zbl 1247.11152
[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.  MR 2904603 |  Zbl pre06051361
[12] D. A. Bini et G. Fiorentino : Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms, 23(2-3) :127–173, 2000.  MR 1772050 |  Zbl 1018.65061
[13] P. B. Borwein : Computational Excursions in Analysis and Number Theory. CMS Books in Mathematics. Springer-Verlag, 2002.  MR 1912495 |  Zbl 1020.12001
[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. In ISSAC ’04 : Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 42–49. ACM Press, 2004.  MR 2126923 |  Zbl 1134.68595
[16] P. Bürgisser, M. Clausen et M. A. Shokrollahi : Algebraic complexity theory. Springer-Verlag, 1997.  MR 1440179 |  Zbl 1087.68568
[17] D. G. Cantor et H. Zassenhaus : A new algorithm for factoring polynomials over finite fields. Math. Comp., 36(154) :587–592, 1981.  MR 606517 |  Zbl 0493.12024
[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. In ISSAC ’04 : Proceedings of the 2004 international symposium on Symbolic and algebraic computation, pages 87–94. ACM Press, 2004.  MR 2126929 |  Zbl 1134.68597
[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.  MR 2161993 |  Zbl 1152.13302
[22] G. Chèze et A. Galligo : From an approximate to an exact absolute polynomial factorization. J. Symbolic Comput., 41(6) :682–696, 2006.  MR 2208507 |  Zbl 1134.13022
[23] G. Chèze et G. Lecerf : Lifting and recombination techniques for absolute factorization. J. Complexity, 23(3) :380–420, 2007.  MR 2330992 |  Zbl 1130.12007
[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.  MR 1285172 |  Zbl 0867.65022
[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.  Zbl 0481.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.  Zbl 0902.14040
[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.  Zbl 1165.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.  MR 1489971 |  Zbl 0927.11055
[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.  MR 675461 |  Zbl 0482.68058
[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.  MR 71385 |  Zbl 0064.24902
[31] A. Fröhlich et J. C. Shepherdson : Effective procedures in field theory. Philos. Trans. Roy. Soc. London. Ser. A., 248 :407–432, 1956.  MR 74349 |  Zbl 0070.03502
[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.  MR 2402428 |  Zbl 1179.68198
[33] M. Fürer : Faster integer multiplication. SIAM J. Comput., 39(3) :979–1005, 2009.  MR 2538847 |  Zbl 1192.68926
[34] Shuhong Gao : Absolute irreducibility of polynomials via Newton polytopes. J. Algebra, 237(2) :501–520, 2001.  MR 1816701 |  Zbl 0997.12001
[35] Shuhong Gao : Factoring multivariate polynomials via partial differential equations. Math. Comp., 72(242) :801–822, 2003.  MR 1954969 |  Zbl 1052.12006
[36] Shuhong Gao et A. G. B. Lauder : Hensel lifting and bivariate polynomial factorisation over finite fields. Math. Comp., 71(240) :1663–1676, 2002.  MR 1933049 |  Zbl 1076.11064
[37] Shuhong Gao et V. M. Rodrigues : Irreducibility of polynomials modulo $p$ via Newton polytopes. J. Number Theory, 101(1) :32–47, 2003.  MR 1979651 |  Zbl 1108.13307
[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).  MR 828524 |  Zbl 0599.68037
[39] J. von zur Gathen et E. Kaltofen : Factorization of multivariate polynomials over finite fields. Math. Comp., 45(171) :251–261, 1985.  MR 790658 |  Zbl 0596.12017
[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.
[41] J. von zur Gathen : Hensel and Newton methods in valuation rings. Math. Comp., 42(166) :637–661, 1984.  MR 736459 |  Zbl 0581.13001
[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).  MR 828523 |  Zbl 0604.68043
[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.  MR 1086727 |  Zbl 1236.68304
[44] J. von zur Gathen et J. Gerhard : Modern computer algebra. Cambridge University Press, New York, 2$^e$ édition, 2003.  MR 2001757 |  Zbl 1055.68168
[45] J. Gerhard : Fast modular algorithms for squarefree factorization and Hermite integration. Appl. Algebra Engrg. Comm. Comput., 11(3) :203–226, 2001.  MR 1815131 |  Zbl 0987.11078
[46] P. Gianni et B. Trager : Square-free algorithms in positive characteristic. Appl. Algebra Engrg. Comm. Comput., 7(1) :1–14, 1996.  MR 1464533 |  Zbl 0874.12009
[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.  MR 2895208
[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.  MR 635127 |  Zbl 0462.68025
[49] P. Henrici : Applied and Computational Complex Analysis, Volume 1, Power Series Integration Conformal Mapping Location of Zero. Wiley Classics Library. Wiley, 1988.  MR 1008928 |  Zbl 0635.30001
[50] G. Hermann : Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Math. Ann., 95(1) :736–788, 1926.  MR 1512302 |  JFM 52.0127.01
[51] D. Hilbert : Ueber die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten. J. Reine Angew. Math., 110, 1892.  JFM 24.0087.03
[52] M. van Hoeij : Factoring polynomials and the knapsack problem. J. Number Theory, 95(2) :167–189, 2002.  MR 1924096 |  Zbl 1081.11080
[53] J. van der Hoeven : New algorithms for relaxed multiplication. J. Symbolic Comput., 42(8) :792–802, 2007.  MR 2345837 |  Zbl 1130.68103
[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.  MR 2996877 |  Zbl 1261.65017
[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.  MR 725671 |  Zbl 0519.14002
[58] E. Kaltofen : Polynomial factorization. In B. Buchberger, G. Collins et R. Loos, éditeurs : Computer algebra, pages 95–113. Springer-Verlag, 1982.  Zbl 0519.68059
[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.
[60] E. Kaltofen : Effective Hilbert irreducibility. Inform. and Control, 66(3) :123–137, 1985.  MR 824125 |  Zbl 0584.12019
[61] E. Kaltofen : Fast parallel absolute irreducibility testing. J. Symbolic Comput., 1(1) :57–67, 1985.  MR 810135 |  Zbl 0599.68038
[62] E. Kaltofen : Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput., 14(2) :469–489, 1985.  MR 784750 |  Zbl 0605.12001
[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.  MR 826553 |  Zbl 0605.12011
[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].
[65] E. Kaltofen : Greatest common divisors of polynomials given by straight-line programs. J. ACM, 35(1) :231–264, 1988.  MR 926181 |  Zbl 0642.68058
[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.  Zbl 0519.68059
[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 1068540 |  Zbl 0773.11078
[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.  MR 1253363 |  Zbl 0773.11078
[69] E. Kaltofen : Effective Noether irreducibility forms and applications. J. Comput. System Sci., 50(2) :274–295, 1995.  MR 1330258 |  Zbl 0844.12006
[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.  Zbl 1068.68709
[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.  MR 2280549
[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.  MR 2289115
[73] E. Kaltofen et V. Shoup : Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67(223) :1179–1197, 1998.  MR 1459389 |  Zbl 0902.11053
[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.  Zbl 0712.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.  MR 1056629 |  Zbl 0712.12001
[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.
[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.
[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.  MR 1729291 |  Zbl 0940.94012
[79] P. Kirrinnis : Partial fraction decomposition in $\mathbb{C}(z)$ and simultaneous Newton iteration for factorization in $\mathbb{C}[z]$. J. Complexity, 14(3) :378–444, 1998.  MR 1646107 |  Zbl 0934.12005
[80] S. C. Kleene : General recursive functions of natural numbers. Mathematische Annalen, 112 :727–742, 1936.  MR 1513071 |  Zbl 0014.19402
[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.  MR 1661859 |  Zbl 0926.14001
[82] D. E. Knuth : The Art of Computer Programming, Volume II : Seminumerical Algorithms. Addison Wesley Longman, 3$^e$ édition, 1998.  MR 378456 |  Zbl 0895.68054
[83] L. Kronecker : Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. reine angew. Math., 92 :1–122, 1882.  JFM 14.0038.02
[84] S. Lang : Algebra, volume 211 de Graduate Texts in Mathematics. Springer-Verlag, 3$^e$ édition, 2002.  MR 1878556 |  Zbl 0984.00001
[85] G. Lecerf : Sharp precision in Hensel lifting for bivariate polynomial factorization. Math. Comp., 75 :921–933, 2006.  MR 2197000 |  Zbl 1125.12003
[86] G. Lecerf : Improved dense multivariate polynomial factorization algorithms. J. Symbolic Comput., 42(4) :477–494, 2007.  MR 2317560 |  Zbl 1127.13021
[87] G. Lecerf : Fast separable factorization and applications. Appl. Alg. Eng. Comm. Comp., 19(2), 2008.  MR 2389971 |  Zbl 1205.12008
[88] G. Lecerf : New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. Appl. Alg. Eng. Comm. Comp., 21(2) :151–176, 2010.  MR 2600710 |  Zbl 1245.12008
[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 1209.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.  MR 682664 |  Zbl 0488.12001
[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.  MR 1689509 |  Zbl 0949.11053
[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.  MR 225972 |  Zbl 0162.37101
[94] M. Mignotte : An inequality about factors of polynomials. Math. Comp., 28 :1153–1157, 1974.  MR 354624 |  Zbl 0299.12101
[95] R. Mines et F. Richman : Separability and factoring polynomials. Rocky Mountain J. Math., 12(1) :43–54, 1982.  MR 649738 |  Zbl 0499.12019
[96] R. Mines, F. Richman et W. Ruitenburg : A course in constructive algebra. Universitext. Springer-Verlag, 1988.  MR 919949 |  Zbl 0725.03044
[97] G. L. Mullen et D. Panario : Handbook of Finite Fields. Discrete Mathematics and Its Applications. Chapman and Hall/CRC, 2013.  Zbl pre06192333
[98] D. Mumford : Algebraic geometry. I Complex projective varieties. Classics in Mathematics. Springer-Verlag, 1995. Reprint of the 1976 edition.  MR 1344216 |  Zbl 0821.14001
[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.  MR 396470 |  Zbl 0301.65029
[101] A. Neff et J. H. Reif : An $O(n^{1+\epsilon } \log b)$ 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.
[102] C. A. Neff et J. H. Reif : An efficient algorithm for the complex roots problem. J. Complexity, 12(2) :81–115, 1996.  MR 1398320 |  Zbl 0888.12005
[103] Phong Q. Nguyen et B. Vallée, éditeurs. The LLL Algorithm. Survey and Applications. Information Security and Cryptography. Springer, 2010.  MR 2722178 |  Zbl 1179.11003
[104] H. Niederreiter : A new efficient factorization algorithm for polynomials over small finite fields. Appl. Algebra Engrg. Comm. Comput., 4(2) :81–87, 1993.  MR 1223850 |  Zbl 0776.11070
[105] H. Niederreiter : Factoring polynomials over finite fields using differential equations and normal bases. Math. Comp., 62(206) :819–830, 1994.  MR 1216262 |  Zbl 0797.11092
[106] A. Nijenhuis et H. Wilf : Combinatorial Algorithms for Computers and Calculators. Academic Press, 1978.  MR 510047 |  Zbl 0476.68047
[107] A. Novocin : Factoring Univariate Polynomials over the Rationals. Thèse de doctorat, Department of Mathematics Florida State University Tallahassee, 2008.  MR 2711958
[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. In Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC ’11, pages 403–412, New York, NY, USA, 2011. ACM Press.  MR 2931990
[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.  JFM 48.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. In STOC ’95 : Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 741–750. ACM Press, 1995.  Zbl 0942.68796
[113] V. Y. Pan : Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31(12) :97–138, 1996.  MR 1418708 |  Zbl 0859.65045
[114] V. Y. Pan : Solving a polynomial equation : some history and recent progress. SIAM Rev., 39(2) :187–220, 1997.  MR 1453318 |  Zbl 0873.65050
[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).  MR 1762403 |  Zbl 1041.65043
[116] V. Y. Pan : Univariate polynomials : nearly optimal algorithms for numerical factorization and root-finding. J. Symbolic Comput., 33(5) :701–733, 2002.  MR 1919911 |  Zbl 1004.65061
[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.  MR 1646666 |  Zbl 0912.68066
[119] D. A. Plaisted : New NP-hard and NP-complete polynomial and integer divisibility problems. Theoret. Comput. Sci., 13 :125–138, 1984.  MR 752098 |  Zbl 0572.68027
[120] J. Renegar : On the worst-case arithmetic complexity of approximating zeros of polynomials. J. Complexity, 3(2) :90–113, 1987.  MR 907192 |  Zbl 0642.65031
[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.  MR 644490 |  Zbl 0461.03016
[122] W. M. Ruppert : Reduzibilität ebener Kurven. J. Reine Angew. Math., 369 :167–191, 1986.  MR 850633 |  Zbl 0584.14012
[123] W. M. Ruppert : Reducibility of polynomials $f(x,y)$ modulo $p$. J. Number Theory, 77(1) :62–70, 1999.  MR 1695700 |  Zbl 0931.11005
[124] T. Sasaki, T. Saito et T. Hilano : Analysis of approximate factorization algorithm. I. Japan J. Indust. Appl. Math., 9(3) :351–368, 1992.  MR 1189944 |  Zbl 0808.12001
[125] T. Sasaki et M. Sasaki : A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10(1) :21–39, 1993.  MR 1208180 |  Zbl 0796.12006
[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.  MR 1137647 |  Zbl 0757.12006
[127] A. Schinzel : Polynomials with special regard to reducibility, volume 77 de Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2000.  MR 1770638 |  Zbl 0956.12001
[128] A. Schönhage : Schnelle Berechnung von Kettenbruchentwicklugen. Acta Inform., 1 :139–144, 1971.  Zbl 0223.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.  MR 594695 |  Zbl 0452.68050
[131] A. Seidenberg : Construction of the integral closure of a finite integral domain. Rend. Sem. Mat. Fis. Milano, 40 :100–120, 1970.  MR 294327 |  Zbl 0218.14023
[132] A. Seidenberg : Constructions in algebra. Trans. Amer. Math. Soc., 197 :273–313, 1974.  MR 349648 |  Zbl 0356.13007
[133] A. Seidenberg : Constructions in a polynomial ring over the ring of integers. Amer. J. Math., 100(4) :685–703, 1978.  MR 509069 |  Zbl 0416.13013
[134] I. R. Shafarevich : Basic algebraic geometry. 1 Varieties in projective space. Springer-Verlag, 2$^e$ édition, 1994.  MR 1328833 |  Zbl 0362.14001
[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.  MR 2167699 |  Zbl 1120.13026
[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.  Zbl 0498.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.  MR 2394991 |  Zbl 1134.68067
[143] B. L. van der Waerden : Eine Bemerkung über die Unzerlegbarkeit von Polynomen. Math. Ann., 102(1) :738–739, 1930.  MR 1512605 |  JFM 56.0825.05
[144] B. L. van der Waerden : Modern Algebra. Vol. I. Frederick Ungar Publishing Co., New York, N. Y., 1949.  MR 29363 |  Zbl 0039.00902
[145] P. S. Wang : An improved multivariate polynomial factoring algorithm. Math. Comp., 32(144) :1215–1231, 1978.  MR 568284 |  Zbl 0388.10035
[146] P. S. Wang et L. P. Rothschild : Factoring multivariate polynomials over the integers. Math. Comp., 29 :935–950, 1975.  MR 396471 |  Zbl 0311.10052
[147] M. Weimann : A lifting and recombination algorithm for rational factorization of sparse polynomials. J. Complexity, 26(6) :608–628, 2010.  MR 2735422 |  Zbl 1236.12001
[148] M. Weimann : Algebraic osculation and application to factorization of sparse polynomials. Found. Comput. Math., 12(2) :173–201, 2012.  MR 2898781 |  Zbl 1252.14007
[149] J.-C. Yakoubsohn : Finding zeros of analytic functions : $\alpha $ theory for secant type methods. J. Complexity, 15(2) :239–281, 1999.  MR 1693876 |  Zbl 0944.65061
[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.  MR 2170867 |  Zbl 1084.65055
[151] H. Zassenhaus : On Hensel factorization I. J. Number Theory, 1(1) :291–311, 1969.  MR 242793 |  Zbl 0188.33703
[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.  MR 575692 |  Zbl 0418.68040
[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.  MR 575692 |  Zbl 0418.68040
[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.  Zbl 0482.68037
[155] R. Zippel : Effective Polynomial Computation. Kluwer Academic Publishers, 1993.  Zbl 0794.11048
Copyright Cellule MathDoc 2017 | Crédit | Plan du site