4.4. КОНЕЧНЫЕ ПОЛЯ; КОЛЬЦАЗ~МНОГОЧЛ ЕНОВ 97

Рис. 4.2. Структура поля GF (4). а ~ представления поля Gf (4); б-арифметические таблицы.

В качестве примера построим поле GF (4) по полю GF (2), используя примитивный многочлен р (х) = + X + 1. Перебирая все возможные разложения, легко проверить неприводимость этого многочлена. Элементы поля задаются многочленами {О, 1, X, X + 1}. Приведенные на рис. 4.2 таблицы сложения и умножения строятся по готовым правилам. Конечно, после того как арифметические таблицы построены, можно заменить многочленные обозначения на целочисленные или другие желаемые обозначения.

Таблица 4.1 содержит список простых многочленов над GF (2). Одним из способов проверки простоты этих многочленов является метод проб и ошибок, т. е. непосредственная проверка всех возможных разложений, хотя для многочленов высоких степеней для этого потребуется ЭВМ. Собранные в табл. 4.1 простые многочлены представляют собой специальные частные случаи простых многочленов, известных под названием примитивных многочленов. Как будет описано в следующем параграфе, они дают наиболее удобное представление расширения поля.

В заключение параграфа подытожим, где мы находимся. Мы разработали необходимые для получения полей построения, которые будут использованы в дальнейшем, но для полного понимания предмета необходимы еще некоторые сведения. В частности, необходимо установить следующие факты: 1) над каждым полем Галуа существуют простые многочлены любой заданной степени; 2) разработанные построения достаточны для получения всех

4 р. Блейхут

Примечание. Все многочлены являются примитивными.

полей Галуа - других полей нет!) ; 3) в каждом поле имеются некоторые предпочтительные, так называемые примитивные элементы.

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

) Математическая строгость требует здесь большего формализма, н надо было бы сказать, что нет других полей с точностью до изоморфизма. Неформально это означает, что любые два поля Галуа с одинаковым числом элементов являются двумя различными представлениями одного и того же поля. Иллюзия другой структуры может быть, например, создана перестановкой тех же самых символов.

Таблица 4.1

Простые многочлены над OF (2)

4.5. примитивные элементы 99

1. Число элементов любого поля Галуа равно степени простого числа.

2. Для любого простого р и целого положительного т наименьшим подполем поля GF (р") является поле GF (р) Элементы поля GF (р) называются целыми числами поля GF {p"), а число р - его характеристикой.

3. В поле Галуа характеристики 2 для каждого элемента р поля выполняется равенство -Р=Р.

4. Для любого простого р и целого положительного т существует поле Галуа с р" элементами.

5. Каждое поле Галуа GF (q) содержит хотя бы один примитивный элемент.

6. Над каждым полем Галуа существует хотя бы один примитивный многочлен любой положительной степени.

7. Каждый примитивный элемент имеет над любым подполем простой минимальный многочлен.

8. Два поля Галуа с одним и тем же числом элементов изоморфны.

9. Для любого q, являющегося степенью простого числа, и любого положительного целого т поле GF (q) является подполем в GF {q"), а GF (q") является расширением поля GF (q).

10. Если п не делит т, то GF (q") не является подполем поля GF iq").

11. Для любого элемента поля GF {q") степень минимального многочлена над GF (q) является делителем т.

Рис. 4.3. Некоторые основные свойства полей Галуа.

доказательству большинства из этих результатов и введению новых понятий. Доказательство существования примитивных многочленов мы откладываем до конца § 5.3.

4.5. ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ

В предыдущем параграфе было построено поле GF (4). На рис. 4.2 видно, что элемент поля, представляемый многочленом х, можно выбрать как бы в качестве некоторого основания логарифмов. За исключением нуля, все элементы поля могут быть представлены в виде степени элемента х.

Определение 4.5.1. Примитивным элементом поля GF (д) называется такой элемент а, что все элементы поля, за исключением нуля„ могут быть представлены в виде степениэлемента а. 4*