Алrебраические структуры над множеством многочленов
Кольцо многочленов над полем GF(p)
Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочленов над конечным по
лем GF(p).
Обозначение. GF[x] - кольцо многочленов f(x) над полем GF(p). F[x] -
кольцо многочленов над полем F.
Для кольца GF[x] справедливы арифметические операции сложения, умножения, сравнения, деления с остатком, делимость.
Два многочлена f(x) и g(x) ÎGF[x] над полем GF(p) считаются
равными тогда и только тогда, когда
f (x)
n
=å
i =0
|
,g ( x)
n
=å
i=0
|
аi. = bi, 0 ≤ i < n .
Сумма многочленов f(x) и g(x) определяется равенством:
n
f ( x) +g ( x) =å(ai
|
Произведение многочленов
i=0
таких, что
f (x)
n
=å
i =0
|
,g ( x)
n
=å
i=0
|
f (x) g ( x)
n+m
=å
|
,ck =
åaibj
k =0
i+ j =k
0 ≤ i ≤ n,, 0 ≤ j ≤ m.
Деление: g(x) ÎGF[x] делит f(x) ÎGF[xJ, если существует многочлен
h(x) ÎGF[x], такой, что f(x) = g(x)h(x).
Деление с остатком. Пусть g(x)≠0 ÎGF[x], тогда для каждого f(x) Î
GF[x] существуют такие q(x) и h(X) ÎGF[x], что
f(x)=q(x)g(x)+h(x), где deg(h)< deg(g) .
В отмеченных равенствах операции сложения и умножения коэффициентов α и β выполняются по модулю простого числа р.
При этом коэффициенты полиномов, являющихся результатом применения операций над полиномами, принадлежат полю GF(p) .
Конечное поле многочленов над GF(p)
Рассмотрим тип поля GF( p n ), n > 1, который основывается на операциях сложения и умножения по модулю неприводимых многочленов
над GF(p) степени n.
В таком поле число элементов равно
p n , а элементы описываются
многочленами над GF(p) степени не выше n -1 в форме
g(x) =
a0 +a1x1 +... +an-1x
n-1
,
где aj ÎGF(p), i = 0,n -1.
Наивысшая степень элемента х равна n -1 , так как операции сложения и умножения многочленов g(x) определены по модулю неприводимого многочлена f(x) над GF(p) степени n. При этом сложение и умножение элементов aj выполняется по модулю р.
Пример .Построим поле GF( p n ) = GF( 22 ). Возьмем неприводимый
многочлен f(x) =
x2 + х + 1 над полем GF(2). Тогда поле GF( 22
= 4) будет
иметь 4 элемента, описываемых многочленами: 0, 1, х, х + 1 (т.е. все многочлены степени, меньшей 2).
Определение 1.18. Два поля GF( p n ), отличающиеся лишь обозначениями элементов, называются изоморфными.
Все поля GF( p n ) изоморфны полю многочленов над GF(p)
по модулю неприводимого многочлена степени n над полем GF(p) [2].
Любое поле GF( p n ) изоморфно конечному полю, полученному
разложением двучлена
pm
|