Geodesic
Factoring polynomials over a finite field and solving systems of algebraic equations
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 20-79 
D. Yu. Grigor'ev. Factoring polynomials over a finite field and solving systems of algebraic equations. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 20-79. http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a2/
@article{ZNSL_1984_137_a2,
     author = {D. Yu. Grigor'ev},
     title = {Factoring polynomials over a~finite field and solving systems of algebraic equations},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {20--79},
     year = {1984},
     volume = {137},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a2/}
}
TY  - JOUR
AU  - D. Yu. Grigor'ev
TI  - Factoring polynomials over a finite field and solving systems of algebraic equations
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1984
SP  - 20
EP  - 79
VL  - 137
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a2/
LA  - ru
ID  - ZNSL_1984_137_a2
ER  - 
%0 Journal Article
%A D. Yu. Grigor'ev
%T Factoring polynomials over a finite field and solving systems of algebraic equations
%J Zapiski Nauchnykh Seminarov POMI
%D 1984
%P 20-79
%V 137
%U http://geodesic.mathdoc.fr/item/ZNSL_1984_137_a2/
%G ru
%F ZNSL_1984_137_a2

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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).