Материал: Методические указания для организации самостоятельной работы по дисциплине «Алгебра и геометрия». Майорова С.П., Завгородний М.Г
f (x) : a(x)
a(x) : r1 (x)
|
x3 2x2 2 |
|
x2 2x 2 |
x3 2x2 2x |
|
|
|
|
x 1 |
||
|
|
|
|
x2 2
x2 2x 2
|
|
|
|
x ( r1) |
|
|
x2 |
2 x 2 |
|
x |
|
|
|||||
x2 |
|
|
x 2 |
||
|
|
|
|||
22xx 2
2 ( r2 )
На последнем шаге алгоритма Евклида при делении r1(x) x на r2 (x) 2 получим нулевой остаток. Тогда, НОД (a, f ) r2 (x) 2 . Линейное представление НОД имеет вид (проверьте!):
2 f (x) (2x 1) a(x) x2 .
Разделив последнее равенство на 2, получим:
1 f (x) (x 2) a(x) 2x2 .
Тогда
[1] |
f |
[ f (x) (x 2)] |
f |
[a(x) 2x2 ] |
f |
. |
|
|
|
|
Отсюда, учитывая равенство [ f (x) (x 2)] f |
[0] f , имеем: |
|||||||
[a(x)] |
f |
[2x2 |
] |
f |
[1] |
f |
. |
|
|
|
|
|
|
|
|||
Последнее равенство означает, что элемент, обратный к классу [a(x)] f , имеет вид:
[a(x)] f 1 [2x2 ] f .
34
Задача 2. Построить поле из восьми элементов. Решение. Так как 8 23 , то в качестве поля P можно
взять 2 {0,1} , а в качестве модуля |
f (x) - неприводимый |
||
многочлен степени n 3 , например, |
f (x) x3 x 1 |
2 |
[x] . |
|
|
|
|
Тогда искомое поле – это 2[x] / f .
Выпишем все элементы этого поля. Для этого рассмотрим всевозможные остатки, которые получаются от деления
на |
f (x) - это многочлены из |
2[x] , |
степень которых 3 , |
||||||
т.е. |
многочлены |
вида |
ax2 bx c , где |
a,b, c |
2 |
{0;1} : |
|||
|
|
|
|
|
|
|
|
|
|
0, 1, x, x 1, x2 , x2 |
1, x2 |
x, x2 |
x 1 . |
Тогда поле |
|
2 |
[x] / f |
||
|
|
|
|
|
|
|
|
|
|
состоит из классов, которые порождаются этими остатками:
2[x]
f (x) {[0], [1], [x], [x 1], [x2 ], [x2 1], [x2 x], [x2 x 1]}
Составим таблицы сложения и умножения для элементов этого поля. Сначала, для примера, найдем сумму и про-
изведение классов [x2 ] и [x2 x] . Для суммы имеем:
[x2 ] [x2 x] [2x2 x] [x] ,
здесь мы сначала сложили два данных многочлена, а затем преобразовали полученные коэффициенты, учитывая, что
2 0(mod 2) .
Теперь найдем произведение классов, для этого сначала перемножим два данных многочлена:
[x2 ] [x2 x] [x4 x3] ,
а затем упростим результат; для этого найдем остаток от де-
ления x4 x3 на модуль |
f (x) x3 x 1 . Имеем: |
35
|
x4 x3 |
|
|
|
x3 x 1 |
|||
x4 |
|
|
|
|
|
|
|
|
|
x2 x |
|
|
|
x 1 |
|||
|
|
x3 |
x2 x |
|
|
|
|
|
|
x3 |
x 1 |
||||||
|
|
|||||||
|
|
|
x2 1 |
|
|
|
||
Окончательно получаем: |
[x2 ] [x2 |
x] [x4 x3] [x2 1] . |
||||||
Аналогично находятся сумма и произведение для всех остальных классов. Таблицы сложения и умножения для поля 2[x]
f выглядят следующим образом (проверьте!):
|
0 |
1 |
x |
x 1 |
x2 |
x2 1 |
x2 x |
x2 x 1 |
0 |
0 |
1 |
x |
x 1 |
x2 |
x2 1 |
x2 x |
x2 x 1 |
1 |
1 |
0 |
x 1 |
x |
x2 1 |
x2 |
x2 x 1 |
x2 x |
x |
x |
x 1 |
0 |
1 |
x2 x |
x2 x 1 |
x2 |
x2 1 |
x 1 |
x 1 |
x |
1 |
0 |
x2 x 1 |
x2 x |
x2 1 |
x2 |
x2 |
x2 |
x2 1 |
x2 x |
x2 x 1 |
0 |
1 |
x |
x 1 |
x2 1 |
x2 1 |
x2 |
x2 x 1 |
x2 x |
1 |
0 |
x 1 |
x |
x2 x |
x2 x |
x2 x 1 |
x2 |
x2 1 |
x |
x 1 |
0 |
1 |
x2 x 1 |
x2 x 1 |
x2 x |
x2 1 |
x2 |
x 1 |
x |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
0 |
1 |
x |
x 1 |
x2 |
x2 1 |
x2 x |
x2 x 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
x |
x 1 |
x2 |
x2 1 |
x2 x |
x2 x 1 |
x |
0 |
x |
x2 |
x2 x |
x 1 |
1 |
x2 x 1 |
x2 1 |
x 1 |
0 |
x 1 |
x2 x |
x2 1 |
x2 x 1 |
x2 |
1 |
x |
x2 |
0 |
x2 |
x 1 |
x2 x 1 |
x2 x |
x |
x2 1 |
1 |
x2 1 |
0 |
x2 1 |
1 |
x2 |
x |
x2 x 1 |
x 1 |
x2 x |
x2 x |
0 |
x2 x |
x2 x 1 |
1 |
x2 1 |
x 1 |
x |
x2 |
x2 x 1 |
0 |
x2 x 1 |
x2 1 |
x |
1 |
x2 x |
x2 |
x 1 |
Тем самым, поле из восьми элементов построено.
36
Задачи и упражнения для самостоятельного решения
1) Сколько элементов содержится в кольце классов вычетов 3[x]
(x2 1) . Обратим ли в этом кольце элемент [2x 1] ?
2) Покажите, что кольцо |
2 |
[x] f , где f (x) x4 |
x3 x 1, |
|
|
|
не является полем. Найдите число его элементов, укажите все обратимые элементы и найдите обратные к ним.
3) Покажите, что многочлен |
f (x) x4 |
x3 x2 3 |
неприво- |
|||
дим над полем 7 . В поле |
|
|
7[x] f |
найдите элемент, об- |
||
ратный для класса [x2 x 3] |
f |
. |
Ответ: [6x3 2x 5] |
f |
||
|
|
|
|
|
||
4) Найдите неприводимый многочлен над полем |
3 , и с его |
|||||
помощью постройте поле из 9 элементов. Составьте таблицы для операций сложения и умножения в этом поле. Для каждого элемента этого поля укажите обратный.
8. КРИТЕРИЙ БАТЛЕРА НЕПРИВОДИМОСТИ МНОГОЧЛЕНА НАД КОНЕЧНЫМ ПОЛЕМ
Основные теоретические сведения
Если поле P конечно, то над ним существуют неприводимые многочлены любой степени. Этот факт значительно усложняет решение вопроса о неприводимости многочлена над данным полем. Приведем критерий неприводимости
многочлена над |
конечным полем, |
установленный |
|
М.Батлером в 1954 |
году. |
|
|
Теорема (критерий Батлера). Многочлен |
f (x) P[x] |
||
степени n неприводим над полем P GF (q) |
тогда и только |
||
тогда, когда выполнены условия: |
|
|
|
1) унитарный НОД ( f , f ) 1 ; |
|
|
|
2) уравнение |
zq z 0 имеет в кольце |
P[x] f (x) |
|
ровно q решений.
37
Из этой теоремы вытекает практически удобный способ распознавания приводимости или неприводимости мно-
гочлена f (x) |
над полем GF (q) . А именно: |
|
|
|
||||||||||
|
1) Если НОД ( f , f ) 1 , то по теореме многочлен f (x) |
|||||||||||||
приводим над GF (q) . |
|
|
|
|
|
|
|
|
|
|
||||
|
2) Пусть НОД ( f , f ) 1 . Тогда проверим, выполняется |
|||||||||||||
ли условие 2 теоремы. |
|
|
|
|
|
|
|
|
|
|||||
|
Построим многочлены |
(x) xiq xi (mod f ) , i |
|
, |
||||||||||
|
1, n 1 |
|||||||||||||
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
такие, |
что |
|
(x) |
0i |
|
x ... |
n 1,i |
xn 1 , |
т.е. многочлен |
|||||
|
|
|
i |
|
1i |
|
|
|
|
|
|
|||
|
(x) |
выполняет роль остатка от деления xiq |
xi на f (x) . |
|||||||||||
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Из коэффициентов многочленов |
i (x) |
составим мат- |
|||||||||||
рицу A , при этом коэффициенты запишем в матрицу столбцами, где первый столбец – всегда нулевой:
00
A .0
01 |
... |
0,n 1 |
|
|
|
11 |
... |
1,n 1 |
|
|
|
|
. |
||||
. |
... |
. |
|
||
|
|||||
|
|
|
|
|
|
n 1,1 |
... |
|
|
|
|
n 1,n 1 |
|
||||
Заметим, что сначала выписываются коэффициенты при меньших степенях x . В силу критерия Батлера многочлен f (x) неприводим над GF (q) тогда и только тогда, когда rang A n 1. В противном случае f (x) - приводим.
Вопросы для самоконтроля
1) Какую степень могут иметь непрводимые многочлены над конечными полями?
2) Приведите примеры многочленов второй, третьей, четвертой степени, неприводимых над полем 3 .
3) Сформулируйте критерий Батлера.
4) Как проверить условия критерия Батлера?
38