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

Определение 1. Пусть p – простое число, q – степень простого числа p, n – натуральное число, f – нормированный многочлен степеyи n с коэффициентами из поля F_p, f (0) ¹ 0. Порядком многочлена f называется такое наименьшее натуральное число d, что

f | (x ^d - 1).

Порядок многочлена обозначаем через ord f.

Пример 1. Так как x ³ – 1 = (x ² + x  + 1)(x + 1), а x ² – 1, x – 1 не делятся на x ² + x  + 1, то порядок многочлена x ² + x  + 1 над полем F ₂ равен 3.

Так как 

x ⁷ – 1 = (x + 1)(x ⁶ + x ⁵  + x ⁴ + x ³  + x ² + x  + 1) = (x + 1)(x ³ + x ²  + 1)(x ³ + x  + 1),

а многочлены x – 1, x ² – 1, x ³ – 1, x ⁴ – 1, x ⁵ – 1, x ⁶ – 1 не делятся на x ³ + x  + 1, то порядок многочлена x ³ + x  + 1 над полем F ₂ равен 7.

Так как 

(x - 1)(x  + 3) (x  + 5) = x ³ + 7 x ² + 7 x – 15 = x ³ - 1,

а многочлены x – 1, x ² – 1 не делятся на x  + 5, то порядок многочлена x  + 5 над полем F ₇ равен 3.

Теорема 1. Если f – нормированный многочлен степени n над полем F_p, f (0) ¹ 0, то

1 £ ord f £ pⁿ -1.

Доказательство. Так как deg f = n, то число возможных остатков от деления многочленов над полем F_p на многочлен f равно pⁿ, в том числе pⁿ – 1 отличных от нуля. В ряду из pⁿ многочленов

каждый из которых не делится на f, заведомо найдутся такие два многочлена xⁱ, x^j, где i > j, что f делит xⁱ - x^j = x^j (x^{i - j} - 1). Так как многочлены x и f по условию взаимно простые, то f  делит x^{i - j} – 1, и при этом 1 £ i - j £ pⁿ – 1. Отсюда следует, что 1 £ ord f £ pⁿ -1.ÿ

Теорема 2. Если f – неприводимый и нормированный над F_p многочлен с корнем q ¹ 0, то

ord f = ord q.

Доказательство. Пусть a = ord f, b = ord q. Имеем f |(x ^a - 1). Поэтому q^a - 1= 0. Так как b = ord q наименьшее натуральное число с этим свойством, то b £. a.

С другой стороны, q^b - 1= 0. Таким образом, многочлены f и x ^b - 1 имеют общий корень q. Так как то f |(x ^b - 1) и a £. b. Отсюда b = a.ÿ

Теорема 3. Если f – неприводимый над F_p многочлен степени n и d = ord f, то

d | (pⁿ - 1).

Доказательство. Пусть q - один из корней многочлена f в его поле разложения H. Так как многочлен f имеет порядок, то q ¹ 0, и поэтому q - элемент мультипликативной группы H * порядка pⁿ - 1. Так как порядок элемента делит порядок группы, то получаем, что ord q | (pⁿ - 1).ÿ

  Имеем f |(x ^a - 1). Поэтому q^a - 1= 0. Так как b = ord q наименьшее натуральное число с этим свойством, то b £. a.

С другой стороны, q^b - 1= 0. Таким образом, многочлены f и x ^b - 1 имеют общий корень q. Так как многочлен f неприводим на полем F_p, то f |(x ^b - 1) и a £. b. Отсюда b = a.ÿ

Определение 2. Неприводимый на полем F_p многочлен f называется примитивным над полем F_p, если

ord а = pⁿ - 1.

Через b_p (n) обозначим число всех примитивных над полем F_p многочленов степени n.

Теорема 4. Число всех примитивных над полем F_p многочленов степени n равно

.                                           (1)

Доказательство. Из теоремы 2 следует, что каждый корень примитивного над F_p многочлена степени n есть примитивный элемент поля F_q, где q = pⁿ. Верно и обратное: каждый примитивный элемент поля F_q – корень какого-нибудь примитивного над полем F_p многочлена степени n. Далее неприводимые над полем F_p и нормированные многочлены f и g тогда и только тогда имеют общий корень в некотором расширении поля F_p, когда они совпадают. По свойству порядка, число элементов поля F_q порядка q – 1 равно j(pⁿ - 1). Так как различные нормированные неприводимые над полем F_p многочлены попарно взаимно простые, то они имеют различные корни. Так как каждый неприводимый над F_p многочлен степени n имеет n различных корней, то получаем, что . Отсюда следует формула (1).ÿ

Пример 2.