4.9. ЛИНЕАРИЗОВАННЫЕ МНОГОЧЛЕНЫ И НОРМАЛЬНЫЕ БАЗИСЫ

Пусть степень простого числа.

Определение. Линеаризованным многочленом над называется многочлен вида где например линеаризованный многочлен над для любого

Пусть корни лежат в расширенном поле Лемма 20. Рассмотрим как векторное пространство над GF(q). Тогда корни образуют подпространство в

Доказательство Если корни то согласно след ствию 3 и лемме 5 при произвольных элементы также являются корнями

Упражнение (29) Показать, что если делит то корни лежащие в образуют подпространство в

Так как то все корней многочлена различны и образуют мерное подпространство в если

Лемма 21 Обратно, пусть -мерное подпространство в Тогда линеаризованный многочлен над

Доказательство Пусть — базис над GF(q) По лемме 18 матрица

обратима Следовательно, уравнения разрешимы в поле относительно Это означает, что элементы являются корнями многочлена

Любая линейная комбинация элементов произвольный элемент из также является корнем многочлена Следова тельно,

Пример Пусть подпространство в состоящее из точек Тогда (см рис 4 5)

— линеаризованный многочлен над

Нормальные базисы. Определение Нормальным базисом поля над называется базис вида

Например, очевидно, является нормальным базисом поля над . В будущих главах мы будем иногда

пользоваться нормальными базисами, и поэтому этот раздел посвящается доказательству того, что такой базис всегда существует.

Линеаризованный многочлен называется -многочленом, если все его коэффициенты лежат в поле Согласно леммам 20 и 21 корни -многочлена образуют подпространство поля (для некоторого над Они обладают еще одним свойством: если принадлежит то и принадлежит (так как Подпространство с таким свойством называется модулем. Если то не имеет кратных корней, и в дальнейшем рассматривается только этот случай.

С другой стороны, если модуль, то согласно лемме — линеаризованный многочлен А так как модуль представляет собой объединение множеств вида то согласно упражнению (14) все коэффициенты многочлена лежат в Таким образом, верна следующая лемма:

Лемма 22. Предположим, что линеаризованный многочлен над Корни многочлена образуют модуль тогда и только тогда, когда является -многочленом.

Пример. Из таблицы поля приведенной на рис. 3.1, легко видеть, что элементы образуют модуль. Соответствующий -многочлен равен

Обычное произведение двух -многочленов не является -многочленом. Определим символическое произведение двух -многочленов равенством

Упражнения. (30). Доказать коммутативность такого произведения, т. е. справедливость равенства Поставим в соответствие -многочлену обычный многочлен Показать, что обычный многочлен, соответствующий многочлену равен

Лемма 23. Если -многочлен равен символическому произведению -многочленов то делится в обычном смысле на и на Наоборот, если -многочлен делится на -многочлен то для некоторого -многочлена

Доказательство. Пусть сначала Тогда так что он делится на и аналогично на Наоборот, предположим, что Тогда, выполняя символическое деление на получаем

где Но так как то долж-. но выполняться равенство

Пример. Рассмотрим -многочлен из предыдущего примера. Имеем

Если многочлен не может быть представлен в виде то он называется символически неприводимым. Корень многочлена называется примитивным, если он не является корнем никакого -многочлена более низкой степени.

Теорема -многочлен у которого всегда имеет примитивный корень. Доказательство. Пусть

— разложение на символически неприводимые делители, где все различны и —степень Тогда степень равна где Так как то все корни однократны.

Если элемент поля то имеется единственный -многочлен наименьшей степени, скажем, для которого является корнем; иными словами, многочлен, всеми корнями которого являются элементы и все их линейные комбинации. Более того, если корень то делится на Следовательно, корень многочлена является примитивным, если он не является корнем никакого его символического делителя. Используя принцип включения и исключения, получаем, что число примитивных корней многочлена равно

Таким образом, всегда имеет примитивный корень.

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

Следовательно, число примитивных корней этого многочлена равно Действительно, элементы являются его примитивными корнями. Пусть теперь

— произвольный -многочлен. Согласно теореме имеет примитивный корень причем — единственный -многочлен

степени имеющий своим корнем. Корнями многочлена являются элементов вида

где и согласно лемме 22 они образуют модуль. У этого модуля, естественно, имеется нормальный базис:

Теперь мы можем доказать основную теорему этого раздела.

Теорема 25. (Теорема о нормальном базисе). В любом поле существует нормальный базис.

Доказательство. Выберем Мы знаем, что корнями являются все элементы поля Предыдущие рассуждения показывают, что в над имеется нормальный базис.

Упражнение. (32). Для полей характеристики 2 доказать, что базис, дополнительный к нормальному базису, также является нормальным.

Предположим теперь, что равно нечетно, так что многочлен не имеет кратных корней. Пусть

— разложение на различные неприводимые множители. Согласно упражнению (31)

По формуле (4.15) число примитивных корней этого многочлена и, следовательно, число элементов порождающих нормальные базисы в равно:

и поэтому нечетно. Число нормальных базисов равной и также нечетно.

Теорема 26. Если нечетно, то в поле существует самодополнительный нормальный базис. Пример. Имеем:

Следовательно, число элементов, порождающих нормальный базис поля GF(2^3) над GF(2), равно Используя таблицу поля, приведенную на рис. 4.5, находим, что в данном случае такой нормальный базис составляют элементы Этот базис является самодополнительным.

Приведем без доказательств следующее усиление теоремы о нормальных базисах.

Теорема 27. (Давенпорт). Любое конечное поле содержит примитивный элемент у такой, что нормальный базис.

Следствие 28. Поле содержит примитивный элемент, след которого равен 1

Задача (нерешенная). (4 1). Найти простое прямое доказательство следствия 28

Упражнение. (33). Показать, что все символически неприводимые -многочлены степени меньше 16 над исчерпываются многочленами

ЗАМЕЧАНИЯ К ГЛ. 4

(см. скан)