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

В математике и компьютерной алгебре факторизация многочлена состоит в разложении его в произведение неприводимых множителей . Такое разложение теоретически возможно и является единственным для многочленов с коэффициентами в любом поле , но для вычисления факторизации с помощью алгоритма необходимы довольно сильные ограничения на поле коэффициентов . На практике алгоритмы были разработаны только для многочленов с коэффициентами в конечном поле , в поле рациональных чисел или в конечно порожденном расширении поля одного из них.

Все алгоритмы факторизации, включая случай многомерных полиномов над рациональными числами, сводят задачу к этому случаю; см. факторизация полиномов . Она также используется для различных приложений конечных полей, таких как теория кодирования ( циклические избыточные коды и коды BCH ), криптография ( криптография с открытым ключом с помощью эллиптических кривых ) и вычислительная теория чисел .

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

Фон

Конечное поле

Теория конечных полей, истоки которой можно проследить до работ Гаусса и Галуа , сыграла свою роль в различных областях математики. Благодаря применимости этой концепции в других разделах математики и наук, таких как информатика, интерес к конечным полям возродился, и это частично связано с важными приложениями в теории кодирования и криптографии . Приложения конечных полей вводят некоторые из этих разработок в криптографию , компьютерную алгебру и теорию кодирования .

Конечное поле или поле Галуа — это поле с конечным порядком (числом элементов). Порядок конечного поля всегда является простым числом или степенью простого числа. Для каждой степени простого числа q = p ^r существует ровно одно конечное поле с q элементами, с точностью до изоморфизма. Это поле обозначается GF ( q ) или F _q . Если p — простое число, GF ( p ) — простое поле порядка p ; это поле классов вычетов по модулю p , и его p элементов обозначаются 0, 1, ..., p −1. Таким образом, a = b в GF ( p ) означает то же самое, что a ≡ b (mod p ) .

Неприводимые многочлены

Пусть F — конечное поле. Что касается общих полей, то непостоянный многочлен f в F [ x ] называется неприводимым над F, если он не является произведением двух многочленов положительной степени. Многочлен положительной степени, не являющийся неприводимым над F , называется приводимым над F .

Неприводимые многочлены позволяют нам строить конечные поля не простого порядка. Фактически, для простой степени q пусть F _q будет конечным полем с q элементами, уникальным с точностью до изоморфизма. Многочлен f степени n больше единицы, который неприводим над F _q , определяет расширение поля степени n , которое изоморфно полю с q ⁿ элементами: элементы этого расширения являются многочленами степени ниже n ; сложение, вычитание и умножение на элемент F _q являются таковыми для многочленов; произведение двух элементов является остатком от деления на f их произведения как многочленов; обратный элемент может быть вычислен с помощью расширенного алгоритма НОД (см. Арифметика алгебраических расширений ).

Из этого следует, что для вычисления в конечном поле не простого порядка нужно сгенерировать неприводимый многочлен. Для этого общепринятым методом является взятие многочлена наугад и проверка его на неприводимость. Для эффективности умножения в поле обычно ищут многочлены вида x ⁿ + ax + b . ^{[ необходима цитата ]}^[1]

Неприводимые многочлены над конечными полями также полезны для генераторов псевдослучайных чисел, использующих регистры сдвига с обратной связью и дискретное логарифмирование по F _{2 ⁿ} .

Число неприводимых мономических многочленов степени n над F _q равно числу апериодических ожерелий , заданных функцией подсчета ожерелий Моро M _q ( n ). Тесно связанная функция ожерелья N _q ( n ) подсчитывает мономические многочлены степени n , которые являются первичными (степень неприводимого); или, альтернативно, неприводимые многочлены всех степеней d, которые делят n. ^[2]

Пример

Многочлен P = x ⁴ + 1 неприводим над Q , но не над любым конечным полем.

На любом расширении поля F ₂ , P = ( x + 1) ⁴ .
В любом другом конечном поле по крайней мере один из чисел −1, 2 и −2 является квадратом, поскольку произведение двух чисел, не являющихся квадратами, является квадратом, и поэтому мы имеем

Если тогда $-1=a^{2},$ $P=(x^{2}+a)(x^{2}-a).$
Если тогда $2=b^{2},$ $P=(x^{2}+bx+1)(x^{2}-bx+1).$
Если тогда $-2=c^{2},$ $P=(x^{2}+cx-1)(x^{2}-cx-1).$

Сложность

Алгоритмы разложения полиномов используют базовые операции над полиномами, такие как произведения, деления, gcd, степени одного полинома по модулю другого и т. д. Умножение двух полиномов степени не выше n можно выполнить за O ( n ² ) операций в F _q с использованием «классической» арифметики или за O ( n log( n ) log(log( n )) ) операций в F _q с использованием «быстрой» арифметики . Евклидово деление (деление с остатком) можно выполнить за те же временные рамки. Стоимость наибольшего общего делителя полиномов степени не выше n можно принять равной O ( n ² ) операций в F _q с использованием классических методов или равной O ( n log ² ( n ) log(log( n )) ) операций в F _q с использованием быстрых методов. Для многочленов h , g степени не выше n возведение в степень h ^q mod g можно выполнить с помощью O (log( q )) полиномиальных произведений, используя метод возведения в степень квадратным методом, то есть O ( n ² log( q )) операций в F _q с использованием классических методов или O ( n log( q )log( n ) log(log( n ))) операций в F _q с использованием быстрых методов.

В приведенных ниже алгоритмах сложность выражается через количество арифметических операций в F _q с использованием классических алгоритмов арифметики многочленов.

Алгоритмы факторинга

Многие алгоритмы факторизации многочленов над конечными полями включают следующие три этапа:

Факторизация без квадратов
Факторизация с различной степенью
Факторизация с равной степенью

Важным исключением является алгоритм Берлекэмпа , который объединяет этапы 2 и 3.

Алгоритм Берлекэмпа

Алгоритм Берлекэмпа исторически важен как первый алгоритм факторизации, который хорошо работает на практике. Однако он содержит цикл по элементам основного поля, что подразумевает, что он применим только для небольших конечных полей. Для фиксированного основного поля его временная сложность полиномиальна, но для общих основных полей сложность экспоненциальна по размеру основного поля.

Факторизация без квадратов

Алгоритм определяет факторизацию без квадратов для многочленов, коэффициенты которых берутся из конечного поля F _q порядка q = p ^m , где p — простое число. Этот алгоритм сначала определяет производную , а затем вычисляет наибольший общий делитель многочлена и его производной. Если он не равен единице, то наибольший общий делитель снова делится на исходный многочлен, при условии, что производная не равна нулю (случай, который существует для непостоянных многочленов, определенных над конечными полями).

Этот алгоритм использует тот факт, что если производная многочлена равна нулю, то это многочлен от x ^p , то есть, если коэффициенты принадлежат F _p , p -я степень многочлена, полученного заменой x на x ^{1/ p} . Если коэффициенты не принадлежат F _p , p -й корень многочлена с нулевой производной получается той же заменой x , завершенной применением инверсии автоморфизма Фробениуса к коэффициентам.

Этот алгоритм работает также над полем нулевой характеристики , с той лишь разницей, что он никогда не входит в блоки инструкций, где вычисляются корни p -й степени. Однако в этом случае алгоритм Юня гораздо эффективнее, поскольку он вычисляет наибольшие общие делители многочленов меньших степеней. Следствием этого является то, что при факторизации многочлена по целым числам не используется следующий алгоритм: сначала вычисляется факторизация без квадратов по целым числам, а для факторизации полученных многочленов выбирается p таким образом, чтобы они оставались бесквадратными по модулю p .

Алгоритм : SFF (разложение на множители без квадратов) Вход : Монический многочлен  f от F _q [ x ], где q = p ^m  Выход : Разложение на множители без квадратов f  R ← 1  # Сделайте w произведением (без кратности) всех множителей f , которые имеют # кратность не делится на p  c ← gcd ( f , f ′) w ← f / c   # Шаг 1: Определить все множители в w  i ← 1 while  w ≠ 1 do  y ← gcd ( w , c ) fac ← w / y  R ← R · fac ⁱ  w ← y ; c ← c / y ; i ← i + 1 end while # c теперь является произведением (с кратностью) оставшихся множителей f  # Шаг 2: Определите все оставшиеся факторы с помощью рекурсии # Обратите внимание, что это множители f , кратность которых делится на p,  если  c ≠ 1, то  c ← c ^{1/ p}  R ← R · SFF ( c ) ^p  end if   Выход ( Р )

Идея состоит в том, чтобы определить произведение всех неприводимых множителей f с одинаковой кратностью. Это делается в два шага. Первый шаг использует формальную производную f для нахождения всех множителей с кратностью, не делящейся на p . Второй шаг определяет оставшиеся множители. Поскольку все оставшиеся множители имеют кратность, делящуюся на p , то есть они являются степенями p , можно просто взять квадратный корень степени p и применить рекурсию.

Пример разложения на множители без квадратов

Позволять

f=x^{11}+2x^{9}+2x^{8}+x^{6}+x^{5}+2x^{3}+2x^{2}+1\in \mathbf {F} _{3}[x],

разложить по полю с тремя элементами.

Алгоритм сначала вычисляет

c=\НОД(f,f')=x^{9}+2x^{6}+x^{3}+2.

Так как производная не равна нулю, то $w = f / c = x 2 + 2$ , и мы входим в цикл while. После одного цикла мы имеем $y = x + 2$ , $z = x + 1$ и $R = x + 1$ с обновлениями $i = 2$ , $w = x + 2$ и $c = x 8 + x 7 + x 6 + x 2 + x +1$ . Второй раз через цикл дает $y = x + 2$ , $z = 1$ , $R = x + 1$ , с обновлениями $i = 3$ , $w = x + 2$ и $c = x 7 + 2 x 6 + x + 2.$ Третий раз через цикл также не меняет $R.$ Для четвертого раза через цикл мы получаем $y = 1$ , $z = x + 2$ , $R = (x + 1)(x + 2) 4$ , с обновлениями $i = 5$ , $w = 1$ и $c = x 6 + 1$ . Так как w = 1, то выходим из цикла while. Так как $c \neq 1$ , то это должен быть идеальный куб. Кубический корень из $c$ , полученный заменой $x 3$ на $x,$ равен $x 2 + 1$ , а рекурсивный вызов процедуры освобождения от квадратов определяет, что он является свободным от квадратов. Поэтому, возводя его в куб и объединяя со значением $R$ до этой точки, получаем свободное от квадратов разложение

f=(x+1)(x^{2}+1)^{3}(x+2)^{4}.

Факторизация с различной степенью

Этот алгоритм разбивает свободный от квадратов многочлен на произведение многочленов, неприводимые множители которых имеют одинаковую степень. Пусть $f \in F q [x]$ степени $n$ — многочлен, который нужно разложить на множители.

Алгоритм Факторизация с разной степенью (DDF) Вход : Монический бесквадратный многочлен  $f \in F q [x]$  Выход : Множество всех пар  $(g, d)$  таких, что  $f$  имеет неприводимый множитель степени  $d$  и  $g$  является произведением всех моноических неприводимых множителей  $f$  степени  $d$  . Begin  while do if  $g$  $\neq 1$  , then ; end if  $i$  $:=$  $i$  $+ 1;$ end while ; if , then ; if , then return  ${($  $f$  $, 1)}$  , else return  $S$  End $i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;$    $\deg f^{*}\geq 2i$    $g=\НОД(f^{*},x^{q^{i}}-x)$     $S:=S\cup \{(g,i)\}$  $f^{*}:=f^{*}/г$      $f^{*}\neq 1$   $S:=S\cup \{(f^{*},\deg f^{*})\}$   $S=\emptyset$

Корректность алгоритма основана на следующем:

Лемма. Для i ≥ 1 многочлен
$x^{q^{i}}-x\in \mathbf {F} _{q}[x]$
является произведением всех монических неприводимых многочленов в F _q [ x ], степень которых делит i .

На первый взгляд, это неэффективно, поскольку подразумевает вычисление НОД многочленов степени, которая экспоненциальна по степени входного многочлена. Однако,

g=\НОД \left(f^{*},x^{q^{i}}-x\right)

может быть заменен на

g=\НОД \left(f^{*},\left(x^{q^{i}}-x\mod f^{*}\right)\right).

Поэтому нам необходимо вычислить:

x^{q^{i}}-x\mod f^{*},

есть два метода:

Метод I. Начнем со значения
$x^{q^{i-1}}\mod f^{*}$
вычисленный на предыдущем шаге и вычислить его q -ю степень по модулю нового f* , используя возведение в степень методом возведения в квадрат. Для этого необходимо
$O\left(\log(q)\deg(f)^{2}\right)$
арифметические операции в F _q на каждом шаге, и таким образом
$O\left(\log(q)\deg(f)^{3}\right)$
арифметические операции для всего алгоритма.

Метод II. Используя тот факт, что q -я степень является линейным отображением над F _{q ,} мы можем вычислить ее матрицу с помощью
$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right)$
операций. Затем на каждой итерации цикла вычисляем произведение матрицы на вектор (с O (deg( f ) ² ) операций). Это влечет за собой общее количество операций в F _{q ,} которое равно
$O\left(\deg(f)^{2}(\log(q)+\deg(f))\right).$
Таким образом, этот второй метод более эффективен и обычно предпочтителен. Более того, матрица, которая вычисляется в этом методе, используется большинством алгоритмов для факторизации равной степени (см. ниже); таким образом, использование ее для факторизации различной степени экономит дополнительное время вычислений.

Факторизация с равной степенью

Алгоритм Кантора–Цассенхауза

В этом разделе мы рассмотрим факторизацию монического бесквадратного одномерного многочлена f степени n над конечным полем F _q , который имеет $r \geq 2$ попарно различных неприводимых множителей, каждый степени d . $f_{1},\ldots ,f_{r}$

Сначала мы описываем алгоритм Кантора и Зассенхауса (1981), а затем вариант, который имеет немного лучшую сложность. Оба являются вероятностными алгоритмами, время работы которых зависит от случайного выбора ( алгоритмы Лас-Вегаса ), и имеют хорошее среднее время работы. В следующем разделе мы описываем алгоритм Шоупа (1990), который также является алгоритмом факторизации с равной степенью, но является детерминированным. Все эти алгоритмы требуют нечетного порядка q для поля коэффициентов. Для получения дополнительных алгоритмов факторизации см., например, книгу Кнута « Искусство программирования», том 2.

Алгоритм Алгоритм Кантора–Цассенхауза. Вход: Конечное поле F _q нечетного порядка q . Монический свободный от квадратов многочлен f в F _q [ x ] степени n = rd , который имеет r ≥ 2 неприводимых множителей, каждый из которых имеет степень d.  Вывод: множество монических неприводимых множителей f . Факторы := { f }; пока Размер(Факторы) < r  do , Выбрать h в F _q [ x ] с deg( h ) < n случайным образом; для каждого u в Factors с deg( u ) > d сделать , если gcd( g , u ) ≠ 1 и gcd( g , u ) ≠ u , то Factors := Factors ; endif endwhile $g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}$       $\,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}$   Факторы возврата

Корректность этого алгоритма основана на том факте, что кольцо F _q [ x ]/ f является прямым произведением полей F _q [ x ]/ f _i , где f _i работает на неприводимых множителях f . Поскольку все эти поля имеют q ^d элементов, компонент g в любом из этих полей равен нулю с вероятностью

{\frac {q^{d}-1}{2q^{d}}}\sim {\tfrac {1}{2}}.

Это означает, что многочлен gcd( g , u ) является произведением множителей g, для которых компонент g равен нулю.

Было показано, что среднее число итераций цикла while алгоритма меньше , что дает среднее число арифметических операций в F _{q ,} равное . ^[3] $2.5\log _{2}r$ $O(dn^{2}\log(r)\log(q))$

В типичном случае, когда d log( q ) > n , эта сложность может быть уменьшена до

O(n^{2}(\log(r)\log(q)+n))

выбрав h в ядре линейного отображения

v\to v^{q}-v{\pmod {f}}

и замена инструкции

g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}

к

g:=h^{\frac {q-1}{2}}-1{\pmod {f}}.

Доказательство валидности такое же, как и выше, заменяя прямое произведение полей F _q [ x ]/ f _i на прямое произведение их подполей с q элементами. Сложность разлагается на для самого алгоритма, для вычисления матрицы линейного отображения (которая может быть уже вычислена в бесквадратной факторизации) и O ( n ³ ) для вычисления ее ядра. Можно отметить, что этот алгоритм работает также, если множители имеют не одинаковую степень (в этом случае количество множителей r , необходимое для остановки цикла while, находится как размерность ядра). Тем не менее, сложность немного лучше, если бесквадратная факторизация выполняется перед использованием этого алгоритма (поскольку n может уменьшаться при бесквадратной факторизации, это снижает сложность критических шагов). $O(n^{2}\log(r)\log(q))$ $O(n^{2}(\log(q)+n))$

Алгоритм Виктора Шупа

Как и алгоритмы предыдущего раздела, алгоритм Виктора Шупа является алгоритмом факторизации с равной степенью. ^[4] В отличие от них, это детерминированный алгоритм. Однако на практике он менее эффективен, чем алгоритмы предыдущего раздела. Для алгоритма Шупа входные данные ограничены полиномами над простыми полями F _p .

Худшая временная сложность алгоритма Шупа имеет фактор Хотя эта сложность экспоненциальна, она намного лучше, чем у предыдущих детерминированных алгоритмов (алгоритм Берлекэмпа), которые имеют $p$ в качестве фактора. Однако существует очень мало полиномов, для которых время вычисления является экспоненциальным, а средняя временная сложность алгоритма является полиномиальной в где $d$ — степень полинома, а $p$ — число элементов основного поля. ${\sqrt {p}}.$ $d\log(p),$

Пусть g = g ₁ ... g _k — искомая факторизация, где g _i — различные монические неприводимые многочлены степени d . Пусть n = deg( g ) = kd . Рассмотрим кольцо R = F _q [ x ]/ g и обозначим также через x образ x в R . Кольцо R является прямым произведением полей R _i = F _q [ x ]/ g _i , а через p _i обозначим естественный гомоморфизм из R на R _i . Группа Галуа поля R _i над F _q является циклической порядка d , порожденной автоморфизмом поля u → u ^p . Отсюда следует, что корни g _i в R _i равны

p_{i}(x),p_{i}(x^{q}),p_{i}\left(x^{q^{2}}\right),\ldots ,p_{i}\left(x^{q^{d-1}}\right).

Как и в предыдущем алгоритме, этот алгоритм использует ту же подалгебру B из R , что и алгоритм Берлекэмпа , иногда называемую «подалгеброй Берлекэмпа» и определяемую как

{\begin{aligned}B&=\left\{\alpha \in R\ :\ p_{1}(\alpha ),\cdots ,p_{k}(\alpha )\in \mathbf {F} _{q}\right\}\\&=\{u\in R\ :\ u^{q}=u\}\end{aligned}}

Подмножество S множества B называется разделяющим множеством , если для каждого 1 ≤ i < j ≤ k существует s ∈ S такое, что . В предыдущем алгоритме разделяющее множество строится путем случайного выбора элементов S . В алгоритме Шупа разделяющее множество строится следующим образом. Пусть s в R [ Y ] таково, что $p_{i}(s)\neq p_{j}(s)$

{\begin{aligned}s&=(Y-x)\left(Y-x^{q}\right)\cdots \left(Y-x^{q^{d-1}}\right)\\&=s_{0}+\cdots +s_{d-1}Y^{d-1}+Y^{d}\end{aligned}}

Тогда является разделяющим множеством, поскольку для i = 1, ..., k (два монических многочлена имеют одинаковые корни). Поскольку g _i попарно различны, для каждой пары различных индексов ( i , j ) по крайней мере один из коэффициентов s _h будет удовлетворять $\{s_{0},\dots ,s_{d-1}\}$ $p_{i}(s)=g_{i}$ $p_{i}(s_{h})\neq p_{j}(s_{h}).$

При наличии разделяющего множества алгоритм Шупа действует так же, как и последний алгоритм предыдущего раздела, просто заменяя инструкцию «выбрать случайный h в ядре линейного отображения » на «выбрать h + i, где h из S , а i из {1, ..., k −1}». $v\to v^{q}-v{\pmod {f}}$

Сложность времени

Как было описано в предыдущих разделах, для факторизации над конечными полями существуют рандомизированные алгоритмы полиномиальной временной сложности (например, алгоритм Кантора–Цассенхауза). Существуют также детерминированные алгоритмы с полиномиальной средней сложностью (например, алгоритм Шупа).

Существование детерминированного алгоритма с полиномиальной сложностью в худшем случае все еще остается открытой проблемой.

Тест Рабина на неприводимость

Как и алгоритм факторизации с различной степенью, алгоритм Рабина ^[5] основан на лемме, изложенной выше. Алгоритм факторизации с различной степенью проверяет каждое d , не превышающее половину степени входного полинома. Алгоритм Рабина использует то преимущество, что для рассмотрения меньшего количества d множители не нужны . В остальном он похож на алгоритм факторизации с различной степенью. Он основан на следующем факте.

Пусть p ₁ , ..., p _k , будут всеми простыми делителями n , и обозначим , для 1 ≤ i ≤ k многочлен f из F _q [ x ] степени n неприводим в F _q [ x ] тогда и только тогда , для 1 ≤ i ≤ k , и f делит . Фактически, если f имеет множитель степени, не делящий n , то f не делит ; если f имеет множитель степени, делящий n , то этот множитель делит по крайней мере один из $n/p_{i}=n_{i}$ $\gcd \left(f,x^{q^{n_{i}}}-x\right)=1$ $x^{q^{n}}-x$ $x^{q^{n}}-x$ $x^{q^{n_{i}}}-x.$

Алгоритм Тест на неприводимость Рабина Вход : Монический многочлен f от F _q [ x ] степени n , p ₁ , ..., p _k все различные простые делители n . Выход : Либо « f неприводим», либо « f приводим». для  j = 1 до k  сделать ; для i = 1 до k сделать ; g  := gcd( f , h ); если g ≠ 1, то вернуть " f является приводимым" и СТОП ; конец для ; ; если g = 0, то вернуть " f является неприводимым", иначе вернуть " f является приводимым" $n_{j}=n/p_{j}$     $h:=x^{q^{n_{i}}}-x{\bmod {f}}$   $g:=x^{q^{n}}-x{\bmod {f}}$

Основная идея этого алгоритма заключается в вычислении, начиная с наименьшего путем повторного возведения в квадрат или использования автоморфизма Фробениуса , а затем взятии соответствующего НОД. Используя элементарную полиномиальную арифметику, вычисление матрицы автоморфизма Фробениуса требует операций в F _q , вычисление $x^{q^{n_{i}}}{\bmod {f}}$ $n_{1},\ldots ,n_{k}$ $O(n^{2}(n+\log q))$

x^{q^{n_{i}}}-x{\pmod {f}}

требует O ( n ³ ) дополнительных операций, а сам алгоритм требует O ( kn ² ) операций, что дает в общей сложности операций в F _q . Используя быструю арифметику (сложность для умножения и деления, а также для вычисления НОД), вычисление путем повторного возведения в квадрат составляет , а сам алгоритм составляет , что дает в общей сложности операций в F _q . $O(n^{2}(n+\log q))$ $O(n\log n)$ $O(n(\log n)^{2})$ $x^{q^{n_{i}}}-x{\bmod {f}}$ $O(n^{2}\log n\log q)$ $O(kn(\log n)^{2})$ $O(n^{2}\log n\log q)$

Смотрите также

Ссылки

КЕМПФЕРТ, Х. (1969) О факторизации многочленов. Кафедра математики, Университет штата Огайо, Колумбус, Огайо 43210
Шуп, Виктор (1996) Гладкость и факторизация многочленов над конечными полями Кафедра компьютерных наук Университета Торонто
Von Zur Gathen, J .; Panario, D. (2001). Факторизация многочленов над конечными полями: обзор. Журнал символических вычислений , том 31, выпуски 1–2, январь 2001 г., 3–17.
Гао Шухун, Панарио Даниэль, Тест и построение неприводимых многочленов над конечными полями Кафедра математических наук, Университет Клемсона, Южная Каролина, 29634–1907, США. и Кафедра компьютерных наук Университета Торонто, Канада M5S-1A4
Шуп, Виктор (1989) Новые алгоритмы поиска неприводимых многочленов над конечными полями Кафедра компьютерных наук Университета Висконсин-Мэдисон
Геддес, Кит О .; Цапор, Стивен Р.; Лабан, Джордж (1992). Алгоритмы компьютерной алгебры. Бостон, Массачусетс: Kluwer Academic Publishers. стр. xxii+585. ISBN 0-7923-9259-0 .

Примечания

^ "Сводимость над $\mathbb{Z}_2$?". Mathematics Stack Exchange . Получено 2023-09-10 .
^ Кристоф Ройтенауэр, Круговые слова и неприводимые полиномы , Ann. наук. математика Квебек, том 12, № 2, стр. 275–285.
^ Флажоле, Филипп; Стейер, Жан-Марк (1982), Автоматы, языки и программирование , Lecture Notes in Comput. Sci., т. 140, Орхус: Springer, стр. 239–251 , doi :10.1007/BFb0012773, ISBN 978-3-540-11576-2
^ Виктор Шоуп, О детерминированной сложности факторизации многочленов над конечными полями, Information Processing Letters 33:261-267, 1990
^ Рабин, Майкл (1980). «Вероятностные алгоритмы в конечных полях». SIAM Journal по вычислительной технике . 9 (2): 273–280 . CiteSeerX 10.1.1.17.5653 . дои : 10.1137/0209024.

Внешние ссылки

Некоторые неприводимые многочлены http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf
Теория поля и Галуа: http://www.jmilne.org/math/CourseNotes/FT.pdf
Поле Галуа:http://designtheory.org/library/encyc/topics/gf.pdf
Факторизация многочленов над конечными полями: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf

[1] "Сводимость над $\mathbb{Z}_2$?". Mathematics Stack Exchange . Получено 2023-09-10 .

[2] Кристоф Ройтенауэр, Круговые слова и неприводимые полиномы , Ann. наук. математика Квебек, том 12, № 2, стр. 275–285.

[3] Флажоле, Филипп; Стейер, Жан-Марк (1982), Автоматы, языки и программирование , Lecture Notes in Comput. Sci., т. 140, Орхус: Springer, стр. 239–251 , doi :10.1007/BFb0012773, ISBN 978-3-540-11576-2

[4] Виктор Шоуп, О детерминированной сложности факторизации многочленов над конечными полями, Information Processing Letters 33:261-267, 1990

[5] Рабин, Майкл (1980). «Вероятностные алгоритмы в конечных полях». SIAM Journal по вычислительной технике . 9 (2): 273–280 . CiteSeerX 10.1.1.17.5653 . дои : 10.1137/0209024.