Geodesic
Cost bound for LLL--Grigoryev method for factoring in $GF(q)[x,y]$
Fundamentalʹnaâ i prikladnaâ matematika, Tome 8 (2002) no. 1, pp. 129-139.

Voir la notice de l'article provenant de la source Math-Net.Ru

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)$. 
@article{FPM_2002_8_1_a10,
     author = {S. D. Mechveliani},
     title = {Cost bound for {LLL--Grigoryev} method for factoring in $GF(q)[x,y]$},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {129--139},
     publisher = {mathdoc},
     volume = {8},
     number = {1},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2002_8_1_a10/}
}
TY  - JOUR
AU  - S. D. Mechveliani
TI  - Cost bound for LLL--Grigoryev method for factoring in $GF(q)[x,y]$
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2002
SP  - 129
EP  - 139
VL  - 8
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2002_8_1_a10/
LA  - ru
ID  - FPM_2002_8_1_a10
ER  - 
%0 Journal Article
%A S. D. Mechveliani
%T Cost bound for LLL--Grigoryev method for factoring in $GF(q)[x,y]$
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2002
%P 129-139
%V 8
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2002_8_1_a10/
%G ru
%F FPM_2002_8_1_a10
S. D. Mechveliani. Cost bound for LLL--Grigoryev method for factoring in $GF(q)[x,y]$. Fundamentalʹnaâ i prikladnaâ matematika, Tome 8 (2002) no. 1, pp. 129-139. http://geodesic.mathdoc.fr/item/FPM_2002_8_1_a10/

[1] Berlekamp E. R., “Factoring polynomials over large finite fields”, Mathematics of Computation, 24 (1970), 713–735 | DOI | MR

[2] Chistov A. L., Grigoryev D. Yu., Polynomial-time factoring of the multivariable polynomials over a global field, Preprint E-5-82 of the Leningrad department of Steklov Mathematical Institute LOMI, USSR, 1982 | MR

[3] Grigorev D. Yu., “Razlozhenie mnogochlenov nad konechnym polem i reshenie sistem algebraicheskikh uravnenii”, Zapiski nauchnykh seminarov LOMI AN SSSR, 137, 1984, 20–79 | MR

[4] Von zur Gathen J., Kaltofen E., “Polynomial-time factorization of multivariate polynomials over finite fields”, Mathematics of Computation, 45, 251–261 | MR | Zbl

[5] Lenstra A. K., “Factoring multivariate polynomials over finite fields”, Journal of Computer and System Sciences, 30 (1985), 235–248 | DOI | MR | Zbl

[6] Lenstra A. K., Lenstra H. W. Jr., Lovasz L., “Factoring polynomials with rational coefficients”, Math. Ann., 261 (1982), 515–534 | DOI | MR | Zbl

[7] Mechveliani S. D., DoCon, the Algebraic Domain Constructor. Manual and program, , Pereslavl-Zalesskii, 1998–2000 http://www.botik.ru/pub/local/Mechveliani/docon/

[8] Mignotte M., Mathématiques pour le caclul formel, Presses Universitaires de France, 1989 ; Mathematics for computer algebra, Springer-Verlag, 1992 | MR | Zbl | MR | Zbl

[9] Yun D. Y. Y., The Hensel Lemma in Algebraic Manipulation, MIT, Cambridge, Mass., 1974; Garland, New York, 1980