Complexity bound of absolute factoring of parametric polynomials

A. Ayad

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 5-29

Résumé

An algorithm is constructed for the absolute factorization of polynomials with algebraically independent parametric coefficients. It divides the parameter space into pairwise disjoint pieces such that the absolute factorization of the polynomials with coefficients in each piece is given uniformly. Namely, for each piece there exist a positive integer $l\leqslant d$, $l$ variables $C_1,\dots,C_l$ algebraically independent over a ground field $F$ and rational functions $b_{J,j}$ of the parameters and of the variables $C_1,\dots,C_l$ such that for any parametric polynomial $f$ with coefficients in this piece, there exist $c_1,\dots,c_l\in\overline{F}$ with $f=\prod_jG_j$ where $G_j=\sum_{|J|}B_{J,j}Z^J$ is absolutely irreducible. Where $Z=(Z_0,\dots,Z_n)$ are the variables of $f$, each $B_{J,j}$ is the value of $b_{J,j}$ at the coefficients of $f$ and $c_1,\dots,c_l$. $\overline{F}$ denotes the algebraic closure of $F$.

Bibliographie

[1] A. V. Aho, J. E. H. Hopcroft, J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Company, Reading, Mass., Menlo Park, Cal., London, 1974 | Zbl

[2] E. R. Berlekamp, “Factoring polynomials over finite fields”, Bell Systems Tech. J., 46 (1967), 1853–1859 | MR | Zbl

[3] E. R. Berlekamp, “Factoring polynomials over large finite fields”, Math. Comp., 24 (1970), 713–735 | DOI | MR

[4] A. Chistov, D. Grigoriev, “Complexity of quantifier elimination in the theory of algebraically closed fields”, LNCS, 176 (1985), 17–31 | MR

[5] A. L. Chistov, “Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time”, J. Sov. Math., 34:4 (1986), 1838–1882 | DOI | Zbl

[6] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Springer, New York, 1995 | MR | Zbl

[7] D. Grigoriev, “Factorization of polynomials over a finite field and the solution of systems of algebraic equations”, J. Sov. Math., 34:4 (1986), 1762–1803 | DOI

[8] D. Grigoriev, “Complexity of quantifier elimination in the theory of ordinary differential equations”, Lect. Notes Computer Science, 378, 1989, 11–25 | MR

[9] D. Coppersmith, S. Winograd, “Matrix multiplication via arithmetic progressions”, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987, 1–6 | MR

[10] J. von zur Gathen, J. Gerhard, Modern Computer algebra, Cambridge University Press, 1999 | MR

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

[12] E. Kaltofen, On the complexity of factoring polynomials with integer coefficients, PhD Thesis, Rensselaer Polytechnic Instit., Troy, NY, December, 1982 | Zbl

[13] E. Kaltofen, “Factorization of polynomials”, Computer Algebra, Springer, Vienna, 1983, 95–113 | MR

[14] A. K. Lenstra, H. W. Lenstra (Jr), L. Lovasz, “Factoring polynomials with rational coefficients”, Math. Ann., 261:4 (1982), 515–534 | DOI | MR | Zbl

[15] M. Mignotte, D. Stefanescu, Polynomials. An Algorithmic Approach, Springer, 1999 | MR | Zbl

[16] M. Mignotte, Mathématiques pour le calcul formel, Presses Univ. de France, Paris, 1989 | MR | Zbl

[17] D. R. Musser, “Multivariate polynomial factorization”, J. ACM, 22:2 (1975), 291–308 | DOI | MR | Zbl

[18] D. R. Musser, Algorithms for polynomial factorization, PhD Thesis and TR 134, Univ. Wisconsin, 1971

[19] J-F. Ragot, Sur la factorisation absolue des polynômes, Thèse à l'université de Limoges, Decembre, 1997

[20] H. Zassenhaus, “On Hensel factorization”, J. Number Theory, 1 (1969), 291–311 | DOI | MR | Zbl