Abstract:
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.