FPM 2002, ТОМ 8, ВЫПУСК 1, СТР. 129-139

ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2002, ТОМ 8, ВЫПУСК 1, СТР. 129-139

Оценка сложности способа ЛЛЛ--Григорьева факторизации в $GF(q)[x,y]$

С. Д. Мешвелиани

Аннотация

Посмотреть как HTML Посмотреть как рисунок Посмотреть в формате LaTeX


Известный LLL метод был приспособлен в статьях
Д. Ю. Григорьева и А. Л. Чистова (1982) и А. К. Ленстры (1985)
для получения факторизации многочлена $f$ из $F[x,y]$ над конечным
полем $F$. А. К. Ленстра выводит оценку сложности с основной частью
$O((\deg_x f)^6 (\deg_y f)^2)$ арифметических действий в $F$.

Работа Д. Ю. Григорьева и А. Л. Чистова имела цель дать способ
некоторой степенной сложности, и подробные оценки не выводились.
Здесь мы показываем, что этот способ
допускает после некоторых поправок лучшую оценку: с основной частью
$ O((\deg_x f)^4 (\deg_y f)^3) $.

Полнотекстовая версия статьи в формате PostScript (61 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k02/k021/k02111t.htm.
Изменения вносились 8 июля 2002 г.

Оценка сложности способа ЛЛЛ--Григорьева факторизации в GF(q)[x,y]

Оценка сложности способа ЛЛЛ--Григорьева факторизации в $GF(q)[x,y]$