Конечные поля

Целые числа по простому модулю – не единственный пример конечных полей. Более общий тип полей используется при рассмотрении таких криптосистем как AES, поточных шифров на основе РСЛОС и криптосистем, на основе эллиптических кривых.

Рассмотрим множество многочленов от переменной x с коэффициентами из F _p. Это множество обозначается через F _p [ x ] и образует кольцо относительно естественных операций суммы и умножения многочленов. Особый интерес представляет случай p = 2.

Пример. В кольце F ₂[ x ] выполнены равенства:

Зафиксируем многочлен f (x) и будем рассматривать остальные элементы кольца F _p [ x ] по модулю f (x). Как и натуральные числа по модулю n, возможные остатки от деления на многочлен f (x), будут образовывать кольцо. Оно обозначается через F _p [ x ]/ f (x) F _p [ x ] (по аналогии с Z / n Z).

Пример. f (x) = x ⁴ + 1 и p = 2. Тогда

так как

По аналогии с целыми числами по модулю n, где рассматривалось сравнение

a · x º b (mod n)

можно поставить аналогичный вопрос и для многочленов. Пусть a, b и f – многочлены из F _p [ x ]. Существование решения уравнения

a · a º b (mod f)

также зависит от НОД (a, f) и также возможны три ситуации. Наиболее интересна ситуация, когда НОД (a, f) = 1.

Многочлен называется неприводимым, если у него нет делителей, отличных от него самого и констант. Неприводимость многочленов - то же самое, что и простота целых чисел. Кольцо F _p [ x ]/ f (x) F _p [ x ] является конечным полем тогда и только тогда, когда многочлен f (x) неприводим.

Рассмотрим два неприводимых многочлена над полем F₂

и .

Возникают два конечных поля

F₁ = F _p [ x ]/ f ₁(x) F _p [ x ] и F₂ = F _p [ x ]/ f ₂(x) F _p [ x ],

каждое состоит из 2⁷ двоичных многочленов (каждый имеет ровно 7 коэффициентов равных 1 или 0), степень которых не превосходит 6. Сложение в обоих полях выглядит одинаково, поскольку при вычислении суммы складываются коэффициенты многочленов по модулю 2. А вот умножаются элементы этих полей по разному:

Действительно ли различны поля F₁ и F₂ или это только кажущееся различие?

Изоморфны ли поля F₁ и F₂?

Изоморфизм: отображение j: F₁ ® F₂, удовлетворяющее двум требованиям:

Для построения изоморфизма между F₁ и F₂ достаточно показать как выражается корень f ₂(x) в виде многочлена от корня f ₁(x).

Изоморфизм существует между любыми двумя конечными полями с одинаковым числом элементов. Все конечные поля совпадают либо с целыми числами по простому модулю, либо с многочленами по модулю неприводимого многочлена.

Теорема. Существует единственное (с точностью до изоморфизма) конечное поле с числом элементов равным степени простого числа.

Конечное поле из q = p^d элементов обозначается символом F _q или GF(q) (поле Галуа из q элементов).

Любое конечное поле K содержит в себе экземпляр поля целых чисел по некоторому простому модулю p, который называется простым подполем поля K. Число элементов простого подполя называется характеристикой поля и обозначается через char K. В частности char F _p = p. На конечном поле характеристики p можно определить отображение Фробениуса:

Ф: F _q ® F _q, Ф(a) = (a ^p)

которое является автоморфизмом (изоморфизмом поля с самим собой). Множество элементов из F _q, остающихся неподвижными при действии Ф, совпадает с его простым подполем:

{a Î F _q | a ^p = a} = F _p.

Это утверждение – обобщение малой теоремы Ферма на случай любых конечных полей.

Ненулевые элементы конечного поля составляют конечную абелеву циклическую группу . Образующая этой группы называется примитивным элементом конечного поля. Примитивный элемент есть в любом конечном поле, их может быть и несколько. Всегда можно найти такой элемент g Î F _q, что любой ненулевой элемент a Î F _q будет представляться в виде

a = g^x

при некотором целом показателе x.

Пример. В поле из восьми многочленов

.

В нем существует 7 ненулевых элементов, а именно

1, a, a + 1, a², a² + 1, a² + a, a² + a + 1,

где a - корень многочлена x ³ + x + 1 (искусственно введенный элемент, удовлетворяющий соотношению a³ + a + 1 = 0, в котором все действия выполняются по модулю 2).

Тогда:

a¹ = a,

a² = a²,

a³ = a + 1,

a⁴ = a² + a,

a⁵ = a² + 1,

a⁶ = a² + a + 1,

a⁷ = 1

и a - примитивный элемент поля . Целые числа по модулю p также имеют примитивный элемент, так как F _p – конечное поле.