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

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

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

Аннотация

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

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

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

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

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