Abstract:
The well-known LLL method was accommodated in papers by D. Yu. Grigoryev and A. L. Chistov (1982) and A. K. Lenstra (1985) for factoring a polynomial $f$ in $F[x,y]$ over a finite field $F$. A. K. Lenstra derives a cost bound for his method with the main summand $O((\deg_x f)^6 (\deg_y f)^2)$ arithmetic operations in $F$. D. Yu. Grigoryev and A. L. Chistov aimed to provide a method of a degree cost bound and did not consider any detailed estimation. Here we show that this method allows, after certain correction, to prove a better bound with the main summand $O((\deg_x f)^4 (\deg_y f)^3)$.