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)^{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}).

All articles are
published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/k02/k021/k02111h.htm

Last modified: July 5, 2002