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/