// функция возвращает результат сложения (вычитания)

// двух полиномов a и b по модулю 2

int gf_sum(int a, int b)

{

    return a ^ b;

}

Умножение в полях Галуа

Открыв учебник математики за третий класс (если мне не изменяет память), мы найдем, что умножение представляет собой многократное сложение и, коль скоро сложение в полях Галуа мы выполнять уже научились, мы имеем все основания считать, что реализация функции умножения не создаст особого труда. Так? А вот и нет! Я всегда знал, что дважды два равно четырем, до конца никогда не верил в это и, впервые столкнувшись с полями Галуа, понял, насколько был прав[2]. Выяснилось, что существуют и такие математики, где дважды два не равно четырем, а операция умножения определяется не через сложение, а совсем по-другому.

Действительно, если попытаться «обернуть» функцию gf_sum в цикл, мы получим то же самое сложение только в профиль. a * b будет равно а, если b четно, и нулю, если b нечетно. Ну и кому такое умножение нужно? Собственно, функция «настоящего» умножения Галуа настолько сложна и ресурсоемка, что для упрощения ее реализации приходится прибегнуть к временному преобразованию полиномов в индексную форму, последующему сложению индексов, выполняемому по модулю GF, и обратному преобразованию суммы индексов в полиномиальную форму.

Что такое индекс? Это - показатель степени при основании два, дающий искомый полином. Например, индекс полинома 8 равен 3 (2³ = 8), а индекс полинома 2 равен 1 (2¹ = 2). Легко показать, что a * b = 2ⁱ * 2^j = 2^(i+j). В частности, 2 * 8 = 2³ * 2¹ = 2⁽³⁺¹⁾ = 2⁴ = 16. Составим следующую табличку и немного поэкспериментируем с ней:

Таблица 1. Таблица полиномов (левая колонка) и соответствующих им степеней двойки (правая колонка)