Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9].

Любой неприводимый над полем GF(p) многочлен степени п делит

 

 

многочлен

x pm - x

 

(также и многочлен

x pm -1

-1) [9]/

 

Неприводимый над полем GF(p) многочлен степени n тогда

 

 

и только тогда делит многочлен

x pm

-x , если число n делит m [9].

 

Порядок многочлена над полем GF(p)

 

 

Определение ,1.16. Пусть f(x) нормированный степени n многочлен над полем GF(p) и f(0)≠0 ; наименьшее натуральное число Т такое,

 

что f(x) | ( xT

-1), называют порядком многочлена f(x)

 

Порядок многочлена иногда называют его периодом.

 

Обозначение. Ord f - порядок многочлена f = f(x).

 

Если f(x) - нормированный многочлен степени п над полем GF(p), f(0)≠0, то

 

[9]

 

l≤ordf≤ p n

-1.

 

Пусть f(x) и g(x) - взаимно простые многочлены над GF(p), тогда:

 

ord f. g = [ordf, ordg]

 

равен наименьшему общему кратному величин ordf, ordg [9].

 

Если f. неприводимый многочлен степени n над полем

 

GF(p), δ=ordf, то δ | ( p n -1) [9].

 

Примитивные полиномы над полем GF(p)

 

 

Неприводимый над полем GF(p) многочлен f(x) степени n называют примитивным над полем GF(p), если [9]

 

ordf= p n

-1.

 

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

 

явля:ется примитивным, если

 

ordf= 2n

-1.

 

Обозначение.

 

многочленов.

в p (n) {n) - число примитивных степени n над полем GF(p)

 

в p (n)

определяется величиной [9]:

 

 

в p

 

(n) =j(n) ,

n

 

где m =

p n -1, j (m) - функция Эйлера (определяющая количество чисел из

 

множества

 

{0, 1,2, ..., m-1}, взаимно простых с m).

 

 

Пример 1.9.

в (4) =j(15) =2 , так как j(15) =8.

2 4