FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2002, VOLUME 8, NUMBER 1, PAGES 129-139
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.
| Main page | Contents of the journal | News | Search |
Location: http://mech.math.msu.su/~fpm/eng/k02/k021/k02111t.htm.
Last modified: July 5, 2002