Лекция: Арифметика целых чисел и полей Галуа

Теория чисел, или высшая арифметика – раздел математики, изучающий целые числа и сходные объекты.

Множество целых чисел (-n, … -1, 0, 1, 2, …n) определяется как замыкание множества натуральных чисел относительно арифметических операций сложения (+) и вычитания (−). Таким образом, сумма, разность и произведение двух целых чисел дает снова целые числа. Оно состоит из натуральных чисел (1, 2, 3…), чисел вида и числа ноль.

Группа целых чисел, последовательно пронумерованных от 0 до 2n-1, содержащая 2n элементов, называется полем Галуа и обозначается GF(q), где q –число элементов поля. Поле Галуа – конечное коммутативное поле.

В поле Галуа определены сложение, вычитание, умножение и деление на ненулевые элементы. Существует нейтральный элемент для сложения — 0 — и для умножения — 1.

Члены групп в обязательном порядке подчиняются ассоциативному (a + (b + c) = (a + b) + c), коммутативному (a + b = b + a) и дистрибьютивному (a × (b + c) = (a × b) + (a × c)) законам, и обрабатываются следующим образом:

1) сумма двух любых членов группы всегда присутствует в данной группе;

2) для каждого члена «а» группы существует тождественный (identity) ему член, обычно записываемый как «e», удовлетворяющий следующему условию: a + e = e + a = a;

3) для каждого члена «a» группы, существует обратный (inverse) ему член «-a», такой, что: a + –a = 0.

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

Сложение в полях Галуа осуществляется без учета переноса и сумма двух членов группы равна: c = (a + b) % 2n, где операция «%» обозначает взятие остатка. Например: (2 + 3) % 4 = 1. Математически это называется «сложением по модулю 4». Сложение по модулю два в полях Галуа тождественно вычитанию и реализуется битовой операцией XOR.

Результат деления одного члена группы на другой, не равный нулю, член в обязательном порядке должен присутствовать в данной группе (см. правило), то несмотря на то, что деление осуществляется в целых числах, оно всегда будет точным (и никогда не будет округленным). Следовательно, если c = a * b, то a = c/b. Другими словами, умножение и деление непротиворечивым образом определено для всех членов группы, за исключением невозможности деления на нуль, причем расширения разрядной сетки при умножении не происходит.

В вычислительной технике наибольшее распространение получили поля Галуа с основанием 2, что объясняется естественностью этих полей с точки зрения машинной обработки, двоичной по своей природе.

Умножение в полях Галуа определяется не через сложение. Функция «настоящего» умножения Галуа настолько сложна и ресурсоемка, что для упрощения ее реализации прибегают к временному преобразованию полиномов в индексную форму, последующему сложению индексов, выполняемому по модулю GF, и обратному преобразованию суммы индексов в полиномиальную форму. В конечном счете, при реализации функции умножения получают то же самое сложение только в профиль: a * b будет равно а, если b четно, и нулю, если b нечетно.

Индекс в данном случае – это показатель степени при основании два, дающий искомый полином. Например, индекс полинома 8 равен 3 (23 = 8), а индекс полинома 2 равен 1 (21 = 2). Легко показать, что a * b = 2i * 2j = 2(i+j). В частности, 8 * 2 = 23 * 21 = 2(3+1) = 24 = 16.

Т.е. арифметика Галуа не оперирует понятиями привычной нам арифметики: например, уравнения типа 2x = 3 в целых числах не разрешимы и ряд индексов не соответствует никаким полиномам! Но в силу того, что количество полиномов всякого поля Галуа равно количеству всевозможных индексов, мы можем определенным образом сопоставить их друг другу, не принимая во внимание тот факт, что с точки зрения обычной математики такое действие не имеет никакого смысла. Конкретная схема сопоставления может быть любой, главное — чтобы она была внутренне непротиворечивой, то есть удовлетворяла всем правилам групп, перечисленным выше.

Деление в полях Галуа осуществляется практически точно так, как и умножение, с той лишь разницей, что индексы не прибавляются, а вычитаются друг из друга: a/b = 2i/2j = 2(i-j). Деление на нуль не допускается.

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

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