Целые числа по простому модулю – не единственный пример конечных полей. Более общий тип полей используется при рассмотрении таких криптосистем как AES, поточных шифров на основе РСЛОС и криптосистем, на основе эллиптических кривых.
Рассмотрим множество многочленов от переменной x с коэффициентами из Fp. Это множество обозначается через Fp[x] и образует кольцо относительно естественных операций суммы и умножения многочленов. Особый интерес представляет случай p = 2.
Пример. В кольце F2[x] выполнены равенства:
Зафиксируем многочлен f(x) и будем рассматривать остальные элементы кольца Fp[x] по модулю f(x). Как и натуральные числа по модулю n, возможные остатки от деления на многочлен f(x), будут образовывать кольцо. Оно обозначается через Fp[x]/f(x)Fp[x] (по аналогии с Z/nZ).
Пример. f(x) = x4 + 1 и p = 2. Тогда
так как
По аналогии с целыми числами по модулю n, где рассматривалось сравнение
a · x º b (mod n)
можно поставить аналогичный вопрос и для многочленов. Пусть a, b и f – многочлены из Fp[x]. Существование решения уравнения
a · a º b (mod f)
также зависит от НОД (a, f) и также возможны три ситуации. Наиболее интересна ситуация, когда НОД (a, f) = 1.
Многочлен называется неприводимым, если у него нет делителей, отличных от него самого и констант. Неприводимость многочленов - то же самое, что и простота целых чисел. Кольцо Fp[x]/f(x)Fp[x] является конечным полем тогда и только тогда, когда многочлен f(x) неприводим.
Рассмотрим два неприводимых многочлена над полем F2
и .
Возникают два конечных поля
F1 = Fp[x]/f1(x)Fp[x] и F2 = Fp[x]/f2(x)Fp[x],
каждое состоит из 27 двоичных многочленов (каждый имеет ровно 7 коэффициентов равных 1 или 0), степень которых не превосходит 6. Сложение в обоих полях выглядит одинаково, поскольку при вычислении суммы складываются коэффициенты многочленов по модулю 2. А вот умножаются элементы этих полей по разному:
Действительно ли различны поля F1 и F2 или это только кажущееся различие?
Изоморфны ли поля F1 и F2?
Изоморфизм: отображение j: F1 ® F2, удовлетворяющее двум требованиям:
Для построения изоморфизма между F1 и F2 достаточно показать как выражается корень f2(x) в виде многочлена от корня f1(x).
Изоморфизм существует между любыми двумя конечными полями с одинаковым числом элементов. Все конечные поля совпадают либо с целыми числами по простому модулю, либо с многочленами по модулю неприводимого многочлена.
Теорема. Существует единственное (с точностью до изоморфизма) конечное поле с числом элементов равным степени простого числа.
Конечное поле из q = pd элементов обозначается символом Fq или GF(q) (поле Галуа из q элементов).
Любое конечное поле K содержит в себе экземпляр поля целых чисел по некоторому простому модулю p, который называется простым подполем поля K. Число элементов простого подполя называется характеристикой поля и обозначается через char K. В частности char Fp = p. На конечном поле характеристики p можно определить отображение Фробениуса:
Ф: Fq ®Fq, Ф(a) = (ap)
которое является автоморфизмом (изоморфизмом поля с самим собой). Множество элементов из Fq, остающихся неподвижными при действии Ф, совпадает с его простым подполем:
{a Î Fq| ap = a} = Fp.
Это утверждение – обобщение малой теоремы Ферма на случай любых конечных полей.
Ненулевые элементы конечного поля составляют конечную абелеву циклическую группу . Образующая этой группы называется примитивным элементом конечного поля. Примитивный элемент есть в любом конечном поле, их может быть и несколько. Всегда можно найти такой элемент g Î Fq, что любой ненулевой элемент a Î Fq будет представляться в виде
a = gx
при некотором целом показателе x.
Пример. В поле из восьми многочленов
.
В нем существует 7 ненулевых элементов, а именно
1, a, a + 1, a2, a2 + 1, a2 + a, a2 + a + 1,
где a - корень многочлена x3 + x + 1 (искусственно введенный элемент, удовлетворяющий соотношению a3 + a + 1 = 0, в котором все действия выполняются по модулю 2).
Тогда:
a1 = a,
a2 = a2,
a3 = a + 1,
a4 = a2 + a,
a5 = a2 + 1,
a6 = a2 + a + 1,
a7 = 1
и a - примитивный элемент поля . Целые числа по модулю p также имеют примитивный элемент, так как Fp – конечное поле.