FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2002, VOLUME 8, NUMBER 1, PAGES 129-139

Cost bound for LLL--Grigoryev method for factoring in $GF(q)[x,y]$

S. D. Mechveliani

Abstract

View as HTML     View as gif image    View as LaTeX source

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)⁶(deg_y f)²) 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)⁴(deg_y f)³).

All articles are published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/k02/k021/k02111h.htm
Last modified: July 5, 2002