|
Fundamentalnaya i Prikladnaya Matematika, 2002, Volume 8, Issue 1, Pages 129–139
(Mi fpm636)
|
|
|
|
Cost bound for LLL–Grigoryev method for factoring in $GF(q)[x,y]$
S. D. Mechveliani Program Systems Institute of RAS
Abstract:
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)$.
Received: 01.02.2001
Citation:
S. D. Mechveliani, “Cost bound for LLL–Grigoryev method for factoring in $GF(q)[x,y]$”, Fundam. Prikl. Mat., 8:1 (2002), 129–139
Linking options:
https://www.mathnet.ru/eng/fpm636 https://www.mathnet.ru/eng/fpm/v8/i1/p129
|
Statistics & downloads: |
Abstract page: | 309 | Full-text PDF : | 179 | References: | 23 | First page: | 2 |
|