184 Гл. 6. Факторизация многочленов над конечными полями

Нетрудно видеть, что справедливо неравенство
		2l − 1		2l−1
	1 +	2vl − 1	2vl	1	,

поскольку v 1. Так как по условию теоремы l 2, то |S| |R |/2. Теорема 6.25 доказана.

Замечание 6.31. В ряде случаев для проверки неприводимости многочленов над конечным простым полем эффективен следующий метод (см. [101]). Пусть p — простое число, f(x) Z/pZ [x], deg f(x) = n. Многочлен f(x) неприводим тогда и только тогда, когда для любого k, 1 k n/2, выполнено равенство

НОД(f(x), xpk − x) = 1.

(6.12)

Действительно, если f(x) приводим, то у него найдется неприводимый делитель g(x), deg g(x) = k n/2. Все корни g(x) лежат в GF(pk), следовательно, являются корнями xpk − x. Поэтому для k = deg g(x) условие (6.12) не будет выполнено. Если же f(x) неприводим, то его корни не будут являться корнями xpk − x при k < n. Алгоритм проверки неприводимости f(x) заключается в проверке условия (6.12) для всех k n/2.

§ 6.7. Заключение

Вкниге [31, гл. 4, заключение] содержится превосходный обзор методов факторизации многочленов над конечными полями. Там же

ввиде обзора описаны различные методы реализации арифметики в конечных полях, арифметики многочленов над конечными полями и методы решения уравнений в конечных полях.

Вгл. 3 книги [89] описан ряд алгоритмов для реализации полиномиальной арифметики над конечными полями и над кольцом целых чисел, а также алгоритмы факторизации многочленов.

Ряд полезных сведений о факторизации многочленов над конечными полями и решении алгебраических уравнений в GF(q) можно найти

вкниге [60, гл. 7]. Там же описан детерминированный метод нахождения неприводимого многочлена над конечным полем, имеющий в предположении расширенной гипотезы Римана полиномиальную сложность,

и метод решения кубических уравнений в GF(q) за O(log4 q) битовых операций (также в предположении расширенной гипотезы Римана). В этой книге содержится и отличный обзор результатов о факторизации многочленов и решении алгебраических уравнений в конечных полях.

§ 6.7. Заключение

185

В работе [272] была разработана новая алгоритмическая техника применительно к алгоритму Кантора—Цассенхауза. С ее помощью многочлен из GF(q) [x], равный произведению различных неприводимых многочленов одинаковой степени, может быть разложен на неприводимые множители в среднем за

O(n(w+1)/2+o(1) + n1+o(1) log q)

операций в GF(q); здесь w — показатель в оценке сложности умножения квадратных матриц. В работе [142] был получен аналогичный результат: для любого , 0 1 существует вероятностный алгоритм факторизации многочлена степени n из GF(q) [x], делающий в среднем

O(n(w+1)/2+(1− ) (w−1)/2 + n1+ +o(1) log q)

арифметических операций в GF(q).

Из вероятностных алгоритмов факторизации многочленов отметим также алгоритмы Бен-Ора, см. [62].

Новый подход к факторизации многочленов над конечными полями был разработан Нидеррайтером, см. [206; 122; 207]. С точки зрения сложности этот метод близок к оригинальному алгоритму Берлекэмпа.

В работе [253] предложен эффективный алгоритм факторизации многочленов в GF(q) [x] со сложностью O(n2,5 + n1+o(1) log q) операций в GF(q), требующий памяти для O(n3/2) элементов GF(q). Оказалось, что на практике этот алгоритм при большом q является в ряде случаев более эффективным, чем все предыдущие методы.

Вработах [250; 252] предложен ряд алгоритмов для нахождения неприводимых многочленов над конечными полями. Работа [249] посвящена вопросам сложности алгоритмов факторизации многочленов над конечными полями.

Работа [141] посвящена разложению многочленов над большими алгебраическими расширениями конечных полей.

Вработе [137] приведен обзор алгоритмов факторизации многочленов.

Для решения систем алгебраических уравнений применяется либо алгоритм Лазара, либо методы, использующие базисы Грёбнера; см. об этом [157; 172; 100; 156; 155; 81; 125].

Отметим здесь также работу [168]. Она посвящена эффективному нахождению изоморфизма между двумя представлениями конечного поля и имеет важные приложения как к задаче дискретного логарифмирования, так и к вопросам факторизации многочленов над конечными полями.