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

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

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

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

Фон

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

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

Конечное поле или поле Галуа — это поле с конечным порядком (числом элементов). Порядок конечного поля всегда равен простому числу или степени простого числа. Для каждой простой степени q = p ^р, существует ровно одно конечное поле с q элементами с точностью до изоморфизма. Это поле обозначается GF ( q ) Fq _или . Если 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 ^н + топор + б . ^{[ нужна ссылка ]}^[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).$

Сложность

Алгоритмы полиномиального факторинга используют основные полиномиальные операции, такие как произведение, деление, НОД, степени одного многочлена по модулю другого и т. д. Умножение двух многочленов степени не выше 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 ^д 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. ^м с p простое число. Этот алгоритм сначала определяет производную , а затем вычисляет НОД полинома и его производной. Если он не равен единице, то НОД снова делится на исходный многочлен при условии, что производная не равна нулю (случай, который существует для непостоянных многочленов, определенных над конечными полями).

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

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

Algorithm: SFF (Square-Free Factorization)
    Input: A monic polynomial f in F_q[x] where q = p^m
    Output: Square-free factorization of f
    R ← 1
   
    # Make w be the product (without multiplicity) of all factors of f that have 
    # multiplicity not divisible by p
    c ← gcd(f, f′)
    w ← f/c 
   
    # Step 1: Identify all factors in 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 is now the product (with multiplicity) of the remaining factors of f
   
    # Step 2: Identify all remaining factors using recursion
    # Note that these are the factors of f that have multiplicity divisible by p
    if c ≠ 1 then
        c ← c^1/p
        R ← R·SFF(c)^p
    end if 
   
    Output(R)

Идея состоит в том, чтобы идентифицировать произведение всех неприводимых множителей 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=\gcd(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 + х 7 + х 6 + х 2 + х +1$ . Второй раз в цикле дает $y = x + 2$ , $z = 1$ , $R = x + 1$ с обновлениями $i = 3$ , $w = x + 2$ и $c = x. 7 + 2x 6 + х + 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$ по $х$ это $х 2 + 1$ , и вызов процедуры без квадратов рекурсивно определяет, что она свободна от квадратов. Следовательно, возведение его в куб и объединение со значением $R$ до этой точки дает разложение без квадратов.

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

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

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

Algorithm Distinct-degree factorization(DDF)
    Input: A monic square-free polynomial   $f \in F q [x]$ 
    Output: The set of all pairs  $(g, d)$ , such that 
              $f$  has an irreducible factor of degree  $d$  and
              $g$  is the product of all monic irreducible factors of  $f$  of degree  $d$ .
    Begin
         $i:=1;\qquad S:=\emptyset ,\qquad f^{*}:=f;$ 
        while  $\deg f^{*}\geq 2i$  do 
             $g=\gcd(f^{*},x^{q^{i}}-x)$ 
            if  $g \neq 1$ , then 
                 $S:=S\cup \{(g,i)\}$ ;
                 $f^{*}:=f^{*}/g$ 
            end if
             $i := i + 1;$ 
        end while;
        if  $f^{*}\neq 1$ , then  $S:=S\cup \{(f^{*},\deg f^{*})\}$ ;
        if  $S=\emptyset$ , then return  ${(f, 1)}$ ,
            else return  $S$ 
    End

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

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

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

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

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

g=\gcd \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$ попарно различных неприводимых множителей. $f_{1},\ldots ,f_{r}$ каждый степени d .

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

Algorithm Cantor–Zassenhaus algorithm.
    Input: A finite field F_q of odd order q.
           A monic square free polynomial f in F_q[x] of degree n = rd, 
                which has r ≥ 2 irreducible factors each of degree d
    Output: The set of monic irreducible factors of f.

    Factors := {f};
    while Size(Factors) < r do,
        Choose h in F_q[x] with deg(h) < n at random;
         $g:=h^{\frac {q^{d}-1}{2}}-1{\pmod {f}}$ 
        for each u in Factors with deg(u) > d do
            if gcd(g, u) ≠ 1 and gcd(g, u) ≠ u, then
                Factors:= Factors $\,\setminus \,\{u\}\cup \{(\gcd(g,u),u/\gcd(g,u))\}$ ;
            endif
    endwhile

    return Factors

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

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

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

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

В типичном случае, когда 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 ]/ fi _{Доказательство справедливости такое же, как и выше, с} прямым произведением их подполей на q элементов. Сложность разлагается на $O(n^{2}\log(r)\log(q))$ для самого алгоритма, $O(n^{2}(\log(q)+n))$ для вычисления матрицы линейного отображения (которая может быть уже вычислена при бесквадратной факторизации) и O ( n ³) для вычисления его ядра. Можно отметить, что этот алгоритм работает и в том случае, если факторы имеют разную степень (в этом случае количество r факторов, необходимое для остановки цикла while, находится как размерность ядра). Тем не менее, сложность немного выше, если перед использованием этого алгоритма выполняется факторизация без квадратов (поскольку n может уменьшаться при факторизации без квадратов, это снижает сложность критических шагов).

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

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

алгоритма Шупа в худшем случае Временная сложность имеет коэффициент ${\sqrt {p}}.$ Несмотря на экспоненциальную сложность, эта сложность намного лучше, чем предыдущие детерминированные алгоритмы (алгоритм Берлекампа), в которых $p$ является фактором. Однако существует очень мало полиномов, для которых время вычисления является экспоненциальным, а средняя временная сложность алгоритма полиномиальна по $d\log(p),$ где $d$ — степень многочлена, а $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 ^п. Отсюда следует, что корни 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 такое, что $p_{i}(s)\neq p_{j}(s)$ . В предыдущем алгоритме разделяющее множество строится путем случайного выбора элементов S . В алгоритме Шупа разделяющее множество строится следующим образом. Пусть s в R [ Y ] таков, что

{\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}}

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

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

Временная сложность

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

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

Критерий неприводимости Рабина

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

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

Algorithm Rabin Irreducibility Test
    Input: A monic polynomial f in F_q[x] of degree n, 
        p₁, ..., p_k all distinct prime divisors of n.
    Output: Either "f is irreducible" or "f is reducible".

    for j = 1 to k do 
         $n_{j}=n/p_{j}$ ;
    for i = 1 to k do 
         $h:=x^{q^{n_{i}}}-x{\bmod {f}}$ ;
        g := gcd(f, h);
        if g ≠ 1, then return "f is reducible" and STOP;
    end for;
     $g:=x^{q^{n}}-x{\bmod {f}}$ ;
    if g = 0, then return "f is irreducible", 
        else return "f is reducible"

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

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

требуется O ( n ³) дальнейших операций, а сам алгоритм требует O ( kn ²) операций, дающих в общей сложности $O(n^{2}(n+\log q))$ операции в F _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)$ операции в F _q .

См. также

Ссылки

КЕМПФЕРТ, Х. (1969) О факторизации полиномов. Математический факультет, Университет штата Огайо, Колумбус, Огайо, 43210.
Шуп, Виктор (1996) Гладкость и факторизация полиномов по конечным полям. Факультет компьютерных наук Университета Торонто.
Фон Цур Гатен, Дж .; Панарио, Д. (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$?" . Математический обмен стеками . Проверено 10 сентября 2023 г.
^ Кристоф Ройтенауэр, Круглые слова и неприводимые многочлены , Ann. наук. математика Квебека, том 12, № 2, стр. 275-285
^ Флажоле, Филипп; Стейяр, Жан-Марк (1982), Автоматы, языки и программирование , Конспекты лекций по вычислительной технике. наук, том. 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$?" . Математический обмен стеками . Проверено 10 сентября 2023 г.

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

[3] Флажоле, Филипп; Стейяр, Жан-Марк (1982), Автоматы, языки и программирование , Конспекты лекций по вычислительной технике. наук, том. 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 .

[1]

[2]

[3]

[4]

[5]