Factoring polynomials over a~finite field and solving systems of algebraic equations

D. Yu. Grigor'ev

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

Résumé

Let $f\in F_q\ae[X_1,\dots,X_n]$ and $\operatorname{deg}_{X_i}(f)$. Set size $L_1(f)=r^n\ae\log_2q$. An algorithm is suggested factoring $f$ within the polynomial in $L_1(f)$, $q$ time (theorem 1.4). Let $f_0,\dots,f_k\in F[X_1,\dots,X_n]$, denote by $L_2$ the size of polynomials $f_0,\dots,f_k$, degrees $\operatorname{deg}(f_i)$ and either $F$ is finite or $F=\mathbb Q$ for simplicity. An algorithm is proposed finding the irreducible compounds of the variety of common roots of the system $f_0=\dots=f_k=0$ within time polynomial in $L_2$, $d^{n^3}$, $q$ (theorem 2.4).