Вычисление в поле Галуа

Не тревожьтесь, все это мы уже делали. Если n - простое число или степень большого простого числа, то мы получаем то, что математики называют конечным полем. В честь этого мы используем p вместо n. В действительности этот тип конечного поля настолько замечателен, что математики дали ему собственное имя - поле Галуа, обозначаемое как GF(p). (В честь Эвариста Галуа, французского математика, жившего в девятнадцатом веке и успевшего значительно продвинуть теорию чисел, прежде чем в 20 лет он был убит на дуэли.)

В поле Галуа определены сложение, вычитание, умножение и деление на ненулевые элементы. Существует нейтральный элемент для сложения - 0 - и для умножения - 1. Для каждого ненулевого числа существует единственное обратное число (это не было бы так, если бы p не было бы простым числом). Выполняются коммутативный, ассоциативный и дистрибутивный законы.

Арифметика поля Галуа широко используется в криптографии. В нем работает вся теория чисел, поле содержит числа только конечного размера, при делении отсутствуют ошибки округления. Многие криптосистемы основаны на GF(p), где p - это большое простое число.

Чтобы еще более усложнить вопрос, криптографы также используют арифметику по модулю неприводимых многочленов степени n, коэффициентами которых являются целые числа по модулю q, где q - это простое число. Эти поля называются GF(qn). Используется арифметика по модулю p(x), где p(x) - это неприводимый многочлен степени n.

Математическая теория, стоящая за этим, выходит далеко за рамки этой книги, хотя я и опишу ряд криптосистем, использующих ее. Если вы хотите попробовать с неприводимыми многочленами, то GF(2³) включает следующие элементы: 0, 1, x, x + 1, x², x² + 1, x² + x, x² + x + 1. Удобный для параллельной реализации алгоритм вычисления обратных значений в GF(2ⁿ) приведен в [421].

При обсуждении полиномов термин "простое число" заменяется термином " неприводимый многочлен". Полином называется неприводимым, если его нельзя представить в виде двух других полиномов (конечно же, кроме 1 и самого полинома). Полином x² + 1 неприводим над целыми числами, а полином x³ + 2 x² + x не является неприводимым, он может быть представлен как x(x + l)(x + 1).

Полином, который в данном поле является генератором, называется примитивным или базовым, все его коэффициенты взаимно просты. Мы снова вернемся к примитивным полиномам, когда будем говорить о сдвиговых регистрах с линейной обратной связью (см. раздел 16.2).

Вычисления в GF(2ⁿ) могут быть быстро реализованы аппаратно с помощью сдвиговых регистров с линейной обратной связью. По этой причине вычисления над GF(2ⁿ) часто быстрее, чем вычисления над GF(p). Так как возведение в степень в GF(2ⁿ) гораздо эффективнее, то эффективнее и вычисление дискретных логарифмов [180, 181, 368, 379]. Дополнительную информацию об этом можно найти в [140].

Для поля Галуа GF(2ⁿ) криптографы любят использовать в качестве модулей трехчлены p(x) = xⁿ + x + 1, так как длинная строка нулей между коэффициентами при xⁿ и x позволяет просто реализовать быстрое умножение по модулю [183]. Полином должен быть примитивным, в противном случае математика не будет работать. xⁿ + x + 1 примитивен для следующих значений n, меньших чем 1000 [1649, 1648]:

1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900

Существуют аппаратные реализации GF(2¹²⁷), где p(x) = x¹²⁷ + x + 1 [1631, 1632, 1129]. Эффективная архитектура аппаратуры возведения в степень для GF(2ⁿ) рассматривается в [147].