Многочлены над конечным полем

 

Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)

 

m

называется выражение

 

f(x) = a0

+ a1 x + … + aт x ,

 

где коэффициенты a i , i = 0,n принадлежат полю GF(p), символ х в многочлене - переменная (если f(x) рассматривается как функция) или неизвестная, необязательно принадлежащая полю GF(p).

Степенью многочлена f(x) называется наибольшее число i,

 

такое, что a i ≠ 0 .

 

Многочлен нулевой степени называется константой. Обозначение. degf(x) = deg(f) - степень многочлена.

Назовем два многочлена над GF(p) равными, если каждый из них соответствует одной и той же последовательности коэффициентов. Отметим следующее. Пусть f(X)=X3+X2 +х и g(X)=X два многочлена над GF(2). В силу данного определения эти многочлены не равны. Если

представить вместо х элементы поля 0 и 1, то получим, что f(0) = 0, f(1) = 1, g(0) = 0, g(l) = 1. Поэтому если рассматривать f(x) и g(x) как функции переменной, определенной в поле по модулю 2, то они будут равны, хотя при рассмотрении их в виде многочленов (т.е. когда интерес представляет после- довательность коэффициентов) они не равны.

Определение 1.14. Многочлен f(x) над полем GF(p) называется нормированным, если его старший коэффициент а.п равен 1.

 

Пример 1.5.Нормированные многочлены третьей степени над полем

 

GF(2): '

 

x3 ;

x3 + 1;

x3 + х;

x3 +

x2 ;

x3 +

x2 + 1;

 

x3 +

x2 + х;

x3 + х + 1;

x3 +

x2 + х + 1.

 

Определение 1.15. Многочлен f(x) над полем GF(p) называется неприводимым над полем GF(p), если он имеет положительную степень и равенство f(x) = gh, (h также многочлен над полем GF(p» может выполняться лишь в том случае, когда либо g,

либо h являются константой.

Пример 1.6. Неприводимые и нормированные многочлены третьей степени над полем GF(2):

 

x2 + х + 1;

 

x2 +

 

x2 + 1 .

 

Обозначение. d I п - целое число d делит целое число п (без остатка);

 

f(x) I g(x) - многочлен f(x) делит многочлен g(x) (без остатка).

Число неприводимых и нормированных степени п многочленов нaд полем GF(p) определяется на основе функции Мебиуса и равно :

 

n

p

a (n) =1 åp d m(d),

n dIn

 

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

 

Пример. n=4, р=2. а2(4)=1/4(24 - 22)=3