Критерий неприводимости многочлена и способы построения неприводимых многочленов над конечным полем

Теорема 1. Многочлен f (x) Î F [ x ] степени n >0 неприводим над полем F = , q = p^m, тогда и только тогда, когда выполняются условия:

1) (f (x), f ¢ (x)) = 1;

2) уравнение

                                                         (1)

имеет в кольце R = F [ x ]/ f (x) ровно p^m решений.

Доказательство. Необходимость. Пусть многочлен f (x) степени n >0 неприводим над полем F. Покажем, что уравнение (1) имеет в кольце R ровно p^m решений. Уравнение (1) имеет в кольце R по крайней мере p^m решений. Это элементы множества

,

где ` a – класс вычетов элемента a Î F по модулю f (x). Действительно,

,

при этом для любых элементов a ₁, a ₂, если a ₁ ¹ a ₂, то f (x) не делит a ₁ - a ₂ и    ` a <sub>1</sub> ¹ ` a ₂.

Так как многочлен f (x) неприводим над F, то он не имеет кратных множителей и многочлены f (x) и f ¢ (x) взаимно простые. Так как в этом случае кольцо R является полем и уравнение (1) не может иметь в кольце R более решений p^m. Таким образом условия 1-2 выполняются.

Достаточность. Пусть выполняются условия 1-2. Тогда уравнение (1) не имеет других решений, кроме элементов поля F. Докажем, что многочлен f (x) неприводим над полем F. Допустим противное, что многочлен f (x) приводим над полем F. Тогда n >1 и существуют такие многочлены f ₁(x), f ₂(x) Î F [ x ] степени >0, что

f (x) = f ₁(x) f ₂(x).

Докажем теперь, что уравнение (1) имеет решение в R \ ` F, и тем самым приходим к противоречию, доказывающему неприводимость f (x). Так как выполняется условие 1, то многочлен f (x) не имеет кратных множителей и многочлены f ₁(x) и f ₂(x) взаимно простые. Тогда существуют такие многочлены u (x), v (x) Î F [ x ], что

u (x), f ₁(x) + v (x) f ₂(x) = 1.                                        (2)

При этом можно считать, что deg u (x) < deg f ₂(x). Так как в противном случае многочлен u (x) можно разделить на f ₂(x) с остатком u (x) = f ₂(x) g (x) + r (x),            deg r (x)<deg f ₂(x) и тогда получаем:

r (x), f ₁(x) + (f ₁(x) g (x)+ v (x)) f ₂(x) = 1.

Далее в равенстве (2) u (x) ¹ 0. В кольце R имеет место равенство для классов

.

Тогда

Следовательно,

и  - решение уравнения (1) в кольце R. При этом Ï ` F, так как

0 < deg u (x), f ₁(x) < deg f (x).ÿ

Способ распознавания приводимости или неприводимости многочлена f (x) Î F [ x ] степени n >1 над полем F.

1) Если (f (x), f ¢ (x)) ¹ 1, то многочлен f (x) – приводим над полем F.

2) Если (f (x), f ¢ (x)) = 1, то подсчитываем число решений многочлен (1) в кольце R.

Произвольный элемент кольца R можно записать в виде

.

Элемент  является решением уравнения (1) тогда и только тогда, когда выполняется равенство

,

которое можно записать в виде

.

Так как , то отсюда получаем

.                  (3)

Для каждого i = 1,…, n -1 существует такой однозначно определенный многочлен

,

что

.

Тогда равенство (3) представляется в виде

.                         (4)

Так как deg f (x) = n, deg a _i (x) < n при i = 1,…, n -1, то равенство (4) равносильно в кольце F [ x ] условию

.                           (5)

Приравнивая коэффициенты в правой и левой частях равенства (4), получим систему линейных уравнений:

которую в матричной форме

AC=0,                                                       (6)

где

.

Таким образом число решений уравнения (1) в кольце R равно числу решений СЛУ (6), т.е. равно  . По теореме 1 многочлен f (x) Î F [ x ] неприводим над полем F = , q = p^m, тогда и только тогда, когда n -rang A =1, т.е. rang A  = n -1.

Используя изложенный выше алгоритм, можно разложить многочлен f (x) Î F [ x ] в случае приводимости в произведение многочленов меньшей степени. Рассмотрим два случая:

1) d (x) = НОД(f (x), f ¢ (x)) ¹ 1.

Если при этом f ¢ (x) ¹ 0, то 0 £ deg f ¢ (x) < n. Значит 0 < deg d (x) < n и f (x) = d (x) f ₁(x), 0 < deg f ₁(x) < n..

Если f ¢ (x) = 0, то из равенств

получаем, что if_i = 0 при   i = 1,…, n. Следовательно, если j = 1,…, n и f_j ¹ 0, то p | j, так как характеристика поля F равна p. Поэтому многочлен f (x) имеет вид

Это в виду равенства

можно записать в виде

где

.

2) (f (x), f ¢ (x)) = 1. Если многочлен f (x) приводим над F, то rang A  < n -1 и существует нулевое решение C = (с ₀, с ₁,…, с _{n -1}), где с _i ¹ 0, при некотором i = 1,…, n -1. Тогда  решение уравнения (1), где

Теорема 2. Пусть q = p^m. Если f (x) Î F_q [ x ] – нормированный многочлен степени > 0 и многочлен h (x)Î F_q [ x ], удовлетворяет условию h (x) ^q º h (x)(mod f (x)), то

.                               (7)

Доказательство. Каждый НОД из правой части равенства (7) делит многочлен f (x). Поскольку многочлены h (x) – с, c Î F_q попарно взаимно простые, то взаимно простыми являются и их НОД с f (x). Тогда сомножители правой части равенства (7) делят многочлен f (x). С другой стороны, многочлен f (x) делит разность

,

а значит f (x) делит правую часть равенства (7). Так как обе части равенства (7) являются нормированными многочленами, каждый из которых делит другой, и значит, они должны совпадать.ÿ

Число различных нормированных неприводимых делителей многочлена f (x) равно k = n – r, где r – ранг матрицы A. Нетривиальные делители многочлена f (x) находим на основании равенства (7) теоремы (2).

Пример 1. Приводим или нет многочлен f (x) = x ⁴ -2 Î F ₃[ x ] над полем F ₃ и в случае его приводимости разложить его на множители.

Так как НОД(f (x), f ¢ (x)) = НОД(x ⁴ -2, x ³) = 1, то имеет место второй случай. Вычислим многочлены a _i (x), i =1, 2, 3.

i =1. x ³ – x º x ³ + 2 x (f (x)), a₁(x) = 0 + 2 x + 0 x ² + x ³.

i =2. Так как x ⁶ º 2 x ² (f (x)), x ⁶ – x ²º 4 x ² º x ² (f (x)), a₂(x) = 0 + 0 x + 1 x ² + 0 x ³.

i =3. Так как x ⁵ º 2 x (f (x)), x ⁹ º 4 x º x (f (x)), x ⁹ – x ³º x + 2 x ³(f (x)), a₃(x) = 0 + 1 x + 0 x ² + 2 x ³.

Тогда система уравнений (6) принимает вид

.                                       (7)

Так как rang A  =2 < 3 = n -1, то многочлен f (x) приводим над полем F ₃ и разлагается на произведение k = n – r = 4 – 2 = 2 неприводимых сомножителей.

Общее решение системы (7) С = (с ₀, с ₁,0, с ₁). Поэтому можно выбрать решение с (x) = x ³ + x уравнения (1) По теореме 2

f (x) = x ⁴ -2 = НОД(x ⁴ -2, x ³ + x)× НОД(x ⁴ -2, x ³ + x - 1)× НОД(x ⁴ -2, x ³ + x - 2).

Находим

НОД(x ⁴-2, x ³ + x) = 1, НОД(x ⁴-2, x ³ + x -1) = x ² + x +2, НОД(x ⁴-2, x ³ + x -2) = x ² +2 x +2,.

Отсюда находим

f (x) = (x ² + x +2)(x ² +2 x +2).

Так как нетривиальных многочленов в разложении два, то они оба неприводимые над полем F_q.

Так как всего нормированных многочленов степени n над полем F_q имеется (q – 1) q^{n -1}, а неприводимых над полем F_q имеется

,

то вероятность случайного выбора неприводимого нормированного многочлена равна

.

Число операций необходимых для проверки на неприводимость одного многочлена имеет порядок qn ³. Следовательно, общее число операций имеет порядок (q - 1) n ⁴.

Существуют более быстрые способы построения неприводимых многочленов с использованием отображений s: F_q [ x ] ® F_q [ x ], t: F_q [ x ] ® F_q [ x ],определяемые формулами:

.       (8)

запишем в виде.

Обозначим, через {a₁,…, a _s } – множество всех его ненулевых корней в поле разложения над F_q. Через 0(f) обозначим НОК мультипликативных порядков элементов a₁,…, a _s: 0(f) = НОК(Ord (a₁),…, Ord (a _s)).

Тогда справедливы теоремы.

Теорема 3. Пусть многочлен f (x)Î F_q [ x ] неприводим над полем F_q, deg f (x) = n, f (x) ¹ x. Тогда многочлен все неприводимы над   полем F_q делители многочлена s(f (x)) имеют степень 0(f).

Теорема 4. Пусть многочлен f (x)Î F_q [ x ] неприводим над полем F_q, deg f (x) = n, f (x) ¹ x. Тогда многочлен s(f (x)) неприводим над полем F_q тогда и только тогда, когда 0(f) = qⁿ - 1.

Пример 2. Пусть 2 ⁿ – 1 – простое число (простое число Мерсенна). Тогда, если многочлен f (x)Î F_q [ x ] неприводим над полем F_q, deg f (x) = n > 1, то из 0(f)| (2 ⁿ – 1) следует, что 0(f) = 2 ⁿ – 1 и по теореме 3 многочлен s(f (x)) неприводим над полем F_q.

Так как числа 2²– 1 = 3, 2³– 1 = 5, 2⁵– 1 = 31, 2⁷– 1 = 127 – простые, то последовательно построим неприводимые над полем F ₂многочлены:

f (x) = x ² + x + 1,

s(f (x)) = x ³ + x + 1,

s²(f (x)) = s(s(f (x))) = x ⁷ + x + 1,

s³(f (x)) =   x ¹²⁷ + x + 1.

5. Конструкция конечного поля из pⁿ элементов

Пусть f – примитивный многочлен над полем F = F_p степени n, q - один из корней многочлена f в его поле разложения. Тогда простое алгебраическое расширение F (q) – простое поле из pⁿ элементов и каждый элемент этого поля однозначно представим в виде

,                              (1)

где a ₀, a ₁, …, a_{n – 1} – элементы поля F.

С каждым выражение (1) сопоставим n -ку элементов поля F

(a ₀, a ₁, …, a_{n – 1}).                                                  (2)

При этом элементы поля F обозначаем значками 0, 1, 2, …, p – 1. Для завершения построения поля из pⁿ элементов укажем, как выполняются операции над n -ками вида (2). Сложение и вычитание выполняется по правилам:

a + b = (a ₀, a ₁, …, a_{n – 1}) + (b ₀, b ₁, …, b_{n – 1}) = (a ₀+ b ₀, a ₁ + b ₁, …, a_{n – 1}+ b_{n – 1}),

a - b = (a ₀, a ₁, …, a_{n – 1}) - (b ₀, b ₁, …, b_{n – 1}) = (a ₀- b ₀, a ₁ - b ₁, …, a_{n – 1}- b_{n – 1}).                                          

Произведение элементов a, b Î F (q) находим следующим образом. Так как

,  ,

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

,  ,

и многочлен a(x)×b(x) разделим на многочлен f (x) с остатком:

a(x)×b(x) = f (x) q (x) + g (x),                                       (3)

где Î F [ x ]. Так как f (q) = 0, то полагая в равенстве (3) x = q получим

a(q)×b(q) = f (q) q (q) + g (q)  = g (q).

Таким образом,

(a ₀, a ₁, …, a_{n – 1})× (b ₀, b ₁, …, b_{n – 1}) = (с ₀, с ₁, …, с _{n – 1}).

Чтобы найти частное элементов a, b Î F (q)

                                             (4)

Так как многочлен f (x) неприводим над полем F и число q не является корнем многочлена b(x), то многочлены f (x) и b(x) взаимно простые. Тогда найдутся такие два многочлена u (x), v (x) Î F [ x ], что

u (x) f (x) + v (x)b(x) = 1.                                           (5)

Так как f (q) = 0, то полагая в равенстве (5) x = q получим

v (q)b(q) = 1.

Используя это равенство и умножая числитель и знаменатель дроби (5) на v (q) получим

После умножения a (q)v(q) в поле F (q) найдем частное элементов a, b.

Пример 1. Многочлен f (x) = x ² + x + 1 неприводим над полем F ₂, q - один из корней многочлена f в его поле разложения. Тогда простое алгебраическое расширение F ₂(q) – простое поле из 2² = 4 элементов и каждый элемент этого поля однозначно представим в виде

,                                (6)

где a ₀, a ₁ – элементы поля F ₂ = {0, 1}. Таблицы сложения и умножения элементов поля F ₂(q) выглядит следующим образом:

+	00	01	10	11		×	00	01	10	11
00	00	01	10	11		00	00	00	00	00
01	01	00	11	10		01	00	01	01	11
10	10	11	00	01		10	00	10	11	01
11	11	10	01	00		11	00	11	01	10

 

 

6.