Polynomial-time factoring of polynomials and finding the compounds of a variety within the aubexponential time

A. L. Chistov

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 124-188

Résumé

Let $F=H(T_1,\dots,T_l)[\eta]$ where either $H=\mathbb Q$or $H$ is a finite field, $T_1,\dots,T_l$ be algebraically independent over $H$, a polynomial $\varphi\in H(T_1,\dots,T_l)[Z]$ be a minimal for $\eta$, denote $q=\operatorname{char}(F)$. Let $L(f)$ be the size of $f\in F[X_0,\dots,X_n]$. THEOREM 1. One can factor $f$ over $F$ within the polynomial in $L(f), L(\varphi), q$ time. The theorem expands the result of [4] treating the case of a finite $F$. Let homogeneous polynomials $f_0,\dots,f_k\in F[X_0,\dots,X_n]$ be given and $\operatorname{deg}_{X_0,\dots,X_n}(f_i)<d$, denote bу $L$ the sise of the system $f_0=\dots=f_k=0$. The variety of common roots in $\mathbb P^n(\bar F)$ of the latter system is decomposable on irreducible compounds $W_\alpha$. A compound $W_\alpha$ is represented further by its general point and by a system of equations whose variety of roots is $W_\alpha$. The following theorem Improves bounds from [4]. THEOREM II. An algorithm is suggested finding all compounds $W_\alpha$ within polynomial in $(Ld^n)^{n+l}$, $q$ time.