"Попросите Якоби или Гаусса публично высказать своё мнение — не о истинности, а о важности этих теорем. Позже, я надеюсь, найдутся люди, которым будет выгодно разобраться во всём этом хаосе."

Этими словами заканчивалось письмо Эвариста Галуа, написанное для своего друга Огюста Шевалье за два дня до его смерти от полученных на дуэли ран на 21 году жизни. Ни Якоби, ни Гаусс в его теоремах не разобрались, зато спустя 15 лет разобрался Жозеф Лиувилль и опубликовал работы Галуа, ставшие впоследствии фундаментом современной алгебры, известные сейчас как теория Галуа. В статье расскажу про одну из частей этой теории - поля Галуа, получившая настолько повсеместное применение в криптографии и избыточном кодировании, что Intel и AMD выпустили набор процессорных расширений для эффективной реализации операций над этими полями.

Заметка! Если вам довелось использовать/реализовывать поля Галуа, то большая часть статьи для вас скорее всего будет не интересна, но возможно в последних разделах будет что-то для вас новое.

• Введение

• Модульная арифметика

• От древней Греции до наших дней

• Вклад Галуа

• Rijndale и Reed-Solomon

• Особенности реализации

  • Стандартная реализация, LUT умножение

  • Построение через башни над

  • Алгоритм Itoh-Tsujii нахождения обратного элемента

  • Intel GFNI

• Ссылки

• Поддержать автора

Что в математике называют полем?

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

• Ассоциативность

• Коммутативность

• Дистрибутивность

• Существование нуля (нейтральный элемент относительно сложения)

• Существование обратного по сложению элемента

• Существование единицы (нейтральной элемент относительно умножения)

• Существование обратного по умножению элемента

Все эти свойства привычны нам по школьной программе для рациональных и вещественных чисел, кто-то возможно и дошел и до комплексных.

Модульная арифметика

Как я уже сказал, ни натуральные, ни целые целые числа не образуют поле из-за отсутствия корректного деления, однако на их основе поле получить можно, для этого нужно перейти к вычислению по модулю.

Лемма 1 (о делении с остатком). Для любых целых чисел существуют единственная пара целых чисел таких, что и

Лемма стандартная, оставлю без доказательства, с её помощью однозначно задаётся операция деления с остатком: - частное, - остаток. Стоит отметить, что такое определение принято в математике, но в программирование обычно деление немного отличается, остаток может получиться отрицательным например при делении отрицательного числа на положительное, в этом случае можно получить положительный остаток если прибавить .

Если обозначить за остаток от деления на , то оказывается, что

ну или если проговорить это словами, то "остаток от деления произведения чисел равен остатку от деления произведения остатков этих чисел". Если всё еще не совсем понятно, то вот частный пример: последняя цифра произведения чисел такая же как у произведения последних цифр этих чисел. Доказывается довольно просто, по лемме о делении с остатком

и соответственно

Левое слагаемое правой части делится на , поэтому не влияет на остаток. Аналогичное свойство работает и с суммой. В итоге получается, что остатки можно складывать и умножать. А можно ли делить? Оказывается что можно, но не всегда.

Лемма 2 (тождество Безу). если взаимно простые, то существуют целые такие, что

Доказывается конструктивно через расширенный алгоритм Евклида. Что это даёт? А вот что

Следствие. Если - простое число, , то существует такое, что

Для доказательства нужно просто применить тождество Безу к . Возвращаясь к аксиомам поля это даёт нам последнее недостающее звено: обратный элемент по умножению.

Пример. Поле остатков по модулю 7 состоит из элементов c таблицей умножения

А обратные по умножению элементы разбиваются на . Таким образом это полноценное поле.

От древней Греции до наших дней

Считается, что описание модульной арифметики в современном виде сделал Гаусс, однако очень многие сопутствующие факты были известны задолго до него:

• Расширенный алгоритм Евклида для решения диофантовых уравнений. Авторство нахождение наибольшего общего делителя однозначно отдают Евклиду, но вот с его расширенной версией не всё так понятно, но в целом справедливо будет назвать его авторами Евклида и Диофанта. Известно ровно два эффективных метода для нахождения обратного элемента в поле остатков по модулю -- расширенный алгоритм Евклида и возведение в степени на основании малой теоремы ферма и теоремы Эйлера, Евклид побеждает по производительности (пишите в комментариях это не так или если на самом деле есть алгоритмы получше).

• Теоремы Сунь Цзы (китайская теорема об остатках) о том, что на интервале существует единственное решение линейной системы сравнений

• Теорема датируется 13-м веком, на просторах интернета можно найти следующее применение, о достоверности которого судить не готов: у генерала батальон примерно на 1000 человек, после очередного боя есть потери, нужно их быстро оценить, пересчитывать каждого по очереди долго, вместо этого можно быстро построить солдат сначала в 3 шеренги, потом в 5, и наконец в 7, попутно запоминая сколько оставалось в последнем ряду. Если потерь было не больше , то этой информации достаточно для того, чтобы эти потери точно посчитать. В современности же на этой теореме основаны например системы остаточных классов: если нужно провести какие-то вычисления на больших числах, то можно сделать провести эти вычисления по модулю различных простых чисел, а потом объединить результат -- в некоторых ситуациях таким образом можно ускорить вычисления, особенно если исходный алгоритм плохо распараллелен.

• Малая теорема Ферма о том, что для простого числа и не делящегося на числа выполняется равенство

• Теорема Эйлера о том, что если обозначить - количество натуральных чисел меньше , являющихся с взаимно простыми, то

Все эти факты лежат в основе современной криптографии, в частности алгоритм Диффи-Хеллмана использует возведение в степени по модулю и опирается на сложность решения задачи дискретного логарифмирования в качестве гарантии надёжности шифрования, а алгоритм RSA опирается на теорему Эйлера и факт о том, что для вычисления для составного числа нужно уметь раскладывать его на множители -- гораздо более сложная задача, чем возведение в степень. Алгоритм Шёнхаге-Штрассена для умножения чисел основан на адаптации алгоритма Кули-Тьюки быстрого преобразования Фурье для конечных полей по модулю простых Ферма - это простые числа вида , удобство которых в существовании первообразного корня из единицы степени .

А что собственно придумал Галуа?

Один из вопросов, которым задался Галуа - какие еще бывают поля с конечным числом элементов кроме полей остатков по простому модулю? Во-первых, стоит отметить, что остатки по составному модулю не образуют поля, например у 2 нет обратного по модулю 4, в общем случае делители модуля (кроме единицы) не будут иметь обратного элемента. Галуа доказал, что существуют поля, состоящие из элементов, где простое, а натуральное; доказал, что других нет; и наконец доказал, что два поля, состоящие из одного числа элементов структурно идентичны. Более формально

Теорема Галуа о конечных полях. Для любого простого числа и натурального числа

• Существует поле , состоящее ровно из элементов

• Если натуральное числа не является степенью простого числа, то не существует поля, состоящего из элементов

• Для любого другого поля также состоящего из элементов существует изоморфизм такой, что

Здесь я ограничусь только частичным доказательством первого пункта, так как он нам позже понадобится. Итак, для мы знаем, что поле существует - поле остатков по модулю, обозначим его . Теперь допустим , давайте посмотрим на множество многочленов степени меньше

Определим сумму как обычно, т.е. отдельно по коэффициентам

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

По аналогии с числами, остаток при делении на - это единственный многочлен степени меньше такой, что для некоторого

Так как остаток при делении на многочлен степени будет иметь степени меньше , то результат такого умножения остается в множестве . Корректность всех свойств поля кроме существования обратного элемента легко проверяется, давайте разбираться с ним.

Возьмем произвольный элемент и посмотрим на последовательность степеней В этой последовательности рано или поздно должно произойти одно из трёх:

• Очередная степень станет равной нулю и все последующие тоже обнуляться

• Очередная степень станет равной единице и дальше последовательность зациклится

• Очередной степень будет равна другой уже присутствующей ранее, но не единице, последовательность зациклица, единица будет только на первом месте

Сначала посмотрим на последнюю ситуацию. Допустим повторилась степень , раз это первое повторение, то значит, что , и при этом или . Оставим это пока и посмотрим на первую ситуацию, допустим оказалось, что , т.е. в частности получается, что . В обоих случаях мы получаем обычное произведение двух многочленов степени меньше делится на . А теперь давайте представим, что изначально мы выбрали таким образом, что у него нет делителей в , тогда вышеописанные ситуации становятся невозможными. Остаётся второй случай когда очередная степени равна единице, т.е. или , т.е. - обратный элемент к a. Таким образом, чтобы конструкция образовывала поле нужен многочлен , не имеющий делителей в - оказывается, что такой многочлен всегда существует, доказательство этого факта приводить не буду.

Конечные поля из элементов часто обозначают как от Galois field.

Поля Галуа в современности: Rijndael и Reed-Solomon

Есть два крупных распространённых применения полей Галуа, которые сводятся к тому, что естественные для компьютера единицы информации - последовательности из байт - можно интерпретировать в виде элемента и проводить над ним какие-то преобразования, которые можно делать только в поле.

Advanced Encryption Standard (AES). Принятый NIST стандарт шифрования, основанный на методе Rijndale, особо ничего про него сказать не могу кроме того, что одна из его составных частей - это несколько побайтовых умножений в . Проконсультировался с коллегами алгебраистами, так если честно и не понял почему и зачем именно такое преобразование используется, напишите в комментариях если знаете зачем. И тем не менее факт в том, что часть AVX-512 сделана специально под этот стандарт для работы с .

Reed-Solomon error correction. Общая идея довольно простая. Представьте, что ваши данные можер представить в виде прямой на плоскости, и вы хотите эти данные передать по ненадёжной сети, где время данные могут потеряться. Чтобы передать вашу прямую достаточно двух точек на этой прямой - из них саму прямую можно однозначно восстановить. Но так как у нас могут потеряться данные, то можно вместо двух точек взять скажем 5 (разных разумеется), тогда чтобы восстановить прямую достаточно, чтобы не потерялись любые две из них. Аналогично например с кругом, который однозначно задаётся тремя точками.

Любые две точки на прямой однозначно задают эту прямую, так как через любые две точки проходит ровно одна прямая. Аналогично любые три из пяти точек на окружности однозначно задают эту окружность, так как через 3 точки может проходить только одна окружность.

Оказывается, что есть обобщение такого подхода: кривая задаётся уравнением , то из интерполяционной теоремы мы знаем что любые точек на этой кривой однозначно выделят её среди других кривых в этом классе. Соответственно алгоритм передачи данных будет выглядеть следующим образом

• Хотим передать последовательность

• Строим многочлен

• Вычисляем и отправляем

• На стороне получателя получили величины с предыдущего шага, что-то потерялось

• Если получили хотя бы n из значений, то проводим интерполяцию и получаем , его коэффициенты - это передаваемое сообщение

• Замечание! Так как передаём мы только , но не сами , то чтобы провести интерполяцию на последнем шаге необходимо знать соответствие , которое обычно известно косвенно из протокола.

Вышеописанная схема почти соответствует простейшей схеме алгоритма Рида-Соломона. Проблема заключается в том, что если всё вышеперечисленное мы делаем над обычными вещественными числами, то из-за ошибок округления эту схему практически нигде не применить. Последний кусочек пазла заключается в том, что всё это можно проделывать в конечном поле, где проблемы ошибок округления нет. В частности последовательность из байт может быть однозначно интерпретирована как коэффициенты многочлена степени меньше , является элементом поля и соответственно также легко представляется в виде байта. Итоге мы получаем протокол, который берёт последовательность из байт, превращает её в последовательность из байт, передаёт её по сети и восстанавливает исходную последовательность если дошли любые из переданных байт.

Особенности реализации полей размера 8k

В основном я буду писать про наиболее распространённое , но обычно верно и для других полей, какие-то уточняющие моменты буду подсвечивать отдельно.

Итак, для построения поля будем использовать представление через многочлены, описанное два раздела назад. Нам понадобится

1. Выбрать способ представления байта в виде элемента GF(256)

Напомню, что элементы - это многочлены степени меньше 8 с коэффициентами 0 или 1, так это же просто 8 битов, давайте хранить коэффициент перед степенью i в i-ом бите байта, например

uint8_t element = 0b00110101; // x^5+x^4+x^2+1

2. Научиться складывать и вычитать

uint8_t Add(uint8_t a, uint8_t b) {
  return a ^ b;
}

uint8_t Subtract(uint8_t a, uint8_t b) {
  return a ^ b;
}

Так, сложение и вычитание у нас определялось просто как обычное сложение и вычитание для многочленов, т.е. по каждой степени по отдельности, а в это просто XOR, соответственно реализация сложения/вычитания очень проста

Ну и сразу отметим, что в 0 является нейтральным по отношению с сложению, а любой элемент является обратным к самому себе по сложению так как x ^ x = 0.

3. Научиться умножать

Так, вот здесь немного хитрее, для начала нам нужен неприводимый в многочлен степени 8. За нас их уже посчитали добрые алгебраисты, их всего 30 выбирайте любой, я возьму вот этот , обозначим его младшие степени в виде отдельного элемента.

const uint8_t irreducible_poly = 0x1b; // x^4+x^3+x+1

Умножение - это у нас обычное умножение многочленов, но с взятием по модулю, который мы только что выбрали. Не хочется очень подробно разжёвывать, вот код умножения в столбик для многочленов

uint8_t Multiply(uint8_t a, uint8_t b) {
  uint8_t result = 0;
  while (a) {
    result ^= b * (a & 1);
    a >>= 1;
    // b << 1 соответствует домножению на многочлена на x
    // (b >> 7) соответветствует проверки, что b
    // многочлен степени 7.
    // ^ (irreducible_poly * (b >> 7)) соответствует
    // взятию по модулю в этом случае. В противном случаем
    // для взятия по модулю ничего не нужно делать
    b = (b << 1) ^ (irreducible_poly * (b >> 7));
  }
  return result;
}

Здесь хочется отметить, что все вычисления производятся над 8 битами, стоит отметить, что b<<1 в реальности вылезет на один бит, но он обрубится при присвоении. Если не совсем понятно почему этот код делает ровно то, что заявлено, добавлю еще аналогичный код обычного умножения в столбик двух чисел по модулю

int MultiplyMod(int a, int b, int mod) {
  int result = 0;
  while (a) {
    result += b * (a & 1);
    a >>= 1;
    b = b << 1; // b <-- 2b
    // До предыдущей операции выполнялось 
    // b < mod, а значит 2b < 2mod-1
    // и для mod достаточно одного вычитания
    if (b > mod)
      b -= mod;
  }
  return result;
}

4. Научиться находить обратный элемент и делить

Так, вот тут нам понадобится еще немножко знаний из алгебры. Следующее утверждение оставлю без доказательства

Лемма 3 (следствия из теоремы Лагранжа для групп). Для любого ненулевого элемента поля выполняется

Более того, существует элемент такой, что степени различны и соответствуют всем элементам поля кроме нуля (такой элемент принято называть примитивным элементом поля).

Таким образом, найти в поле можно например как .

uint8_t Inverse(uint8_t a) {
  uint8_t result = 1;
  uint8_t pow = 254;
  while (pow) {
    if (pow & 1)
      result = Multiply(result, a);
    a = Multiply(a, a);
    pow >>= 1;
  }
  return result;
}

На этом базовая реализация заканчивается …

LUT для умножения и обращения

Для начала стоит отметить, что таблицу умножения для можно просто посчитать в виде двумерного массива размера , что в целом годится для , но для уже неприменимо. Но есть более элегантный способ, у нас есть примитивный элемент , для с порождающим многочленом это например (3 в битовой записи), любой элемент представим в виде степени примитивного, соответственно если , то . И при этом мы знаем, что . Из этих свойств возникает следующая идея

• Подсчитаем таблицу степеней , т.е.

• Подсчитаем таблицу логарифмов , т.е. .

• Получаем

uint8_t exp[256];
uint8_t log[255];
const uint8_t primitive_element = 3;

uint8_t InitTables() {
  uint8_t x = 1;
  for (size_t i = 0; i < 255; i++) {
    exp[i] = x;
    log[x] = i;
    x = Multiply(x, primitive_element);
  }
  exp[255] = 1;
}

uint8_t MultiplyLUT(uint8_t a, uint8_t b) {
  if (a == 0 || b == 0)
    return 0;
  auto p = log[a] + log[b];
  // Во всех случаях кроме log[a]+log[b]=255
  // получаем эквивалент p % 255, если же
  // log[a]+log[b]=255, то пользуемся тем, что
  // exp[255] = 1
  return exp[(p & 255) + (p >> 8)];
}

Такие таблицы занимают байт, аналогичные для занимала бы байт.

Наконец стоит отметить, что для обращения эти таблица тоже можно использовать

uint8_t InverseLUT(uint8_t a) {
  if (a == 0)
    return 0;
  return exp[255 - log[a]];
}

Построение через башни

Указанная выше конструкция с построением через многочлены работает для любого базового поля. Мы делали расширение до , но так же например можно делать расширение до , для этого нужно проделать аналогичную конструкцию с многочленами степени меньше с коэффициентами из . Технически удобно строить поля последовательностью расширений, например каждое из полей можно получить из предыдущего расширением многочленами первой степени. Вот пример как можно получить последнее расширение. Нам понадобится неприводимый многочлен степени 2 над , например многочлен вида

в половине случае является неприводимым (верно для ), возьмём . Элементы нашего расширения имеют вид

Со сложением как и раньше все просто - это побитовый XOR. А что с умножением? Допустим пытаемся умножить a на b, для этого как и раньше умножить многочлены как обычно, а потом поделить с остатком на , здесь удобно использовать трюк, что это деление эквивалентно замене .

А вот как это будет выглядеть в коде

uint16_t Multiply(uint16_t a, uint16_t b) {
  // a = a_0 + a_1x, b = b_0 + b_1x
  // все отдельные элементы из GF(256)
  uint8_t a_0 = a & 255;
  uint8_t a_1 = a >> 8;
  uint8_t b_0 = b & 255;
  uint8_t b_1 = b >> 8;

  auto t = gf_2_8::MultiplyLUT(a_1, b_1);
  auto low_bits =
      gf_2_8::Add(gf_2_8::MultiplyLUT(a_0, b_0), gf_2_8::MultiplyLUT(t, delta));
  auto high_bits = gf_2_8::Add(
      gf_2_8::Add(gf_2_8::MultiplyLUT(a_0, b_1), gf_2_8::MultiplyLUT(a_1, b_0)),
      t);
  return low_bits + (high_bits << 8);
}

Алгоритм нахождения обратного элемента Itoh–Tsujii

Можно нахождение обратного элемента можно сделать через возведение в степень, но есть алгоритм, позволяющий сократить количество умножений. В общем виде идея выглядит так: в поле . Если обозначить , то

Вот здесь есть два интересных момента:

• . Без доказательства

• Так как , то , инверсия происходит в поле

Применительно к полям и получаем следующий алгоритм

• 

• Вычисляем и в

• Вычисляем в

• 

Конкретно в данном случае мы уменьшили количество умножений в почти в 4 раза: вычисление влоб

А алгоритму Itoh-Tsujii нужно 8 умножений для подсчета и еще одно для .

uint16_t InvIT(uint16_t a) {
  uint16_t a_r = a;
  for (size_t i = 0; i < 8; ++i) {
    a_r = Multiply(a_r, a_r);
  }
  uint8_t a_r1 = Multiply(a_r, a);
  // Подсчет обратного элемента из GF(256)
  return Multiply(a_r, gf_2_8::Inv(a_r1));
}

Intel Galois Field New Instruction (GFNI)

Из-за популярности и важности интел выпустили набор расширений для вычислений в этом поле, произошло это кстати не так давно, в 2021 году. Общий принцип этого расширения заключается в следующем. Поле в том числе является линейных пространством размера 8 над полем , функция умножения на элемент a

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

void InitGFNI(void) {
  for (int16_t y = 0; y < 256; ++y) {
    gfni_matrix[y] = 0;
    element_t row = y;
    for (size_t i = 0, shift = 0; i < 8; ++i, shift += 8) {
      gfni_matrix[y] |= ((uint64_t)row << shift);
      row = (row << 1) ^ ((row >> 7) * irreducible_poly);
    }
  }
}

element_t MultiplyGFNI(element_t a, element_t b) {
  return ((a & 1) * (gfni_matrix[b] & 255)) ^
         (((a >> 1) & 1) * ((gfni_matrix[b] >> 8) & 255)) ^
         (((a >> 2) & 1) * ((gfni_matrix[b] >> 16) & 255)) ^
         (((a >> 3) & 1) * ((gfni_matrix[b] >> 24) & 255)) ^
         (((a >> 4) & 1) * ((gfni_matrix[b] >> 32) & 255)) ^
         (((a >> 5) & 1) * ((gfni_matrix[b] >> 40) & 255)) ^
         (((a >> 6) & 1) * ((gfni_matrix[b] >> 48) & 255)) ^
         (((a >> 7) & 1) * ((gfni_matrix[b] >> 56) & 255));
}

Интересно, что сами разработчики Intel в технической документации предлагают в качестве применения для такого подхода например перетасовывание битов в числе. Забавно, что эту идею реализовали в Clang 19 где __builtin_bitreverse64 компилируется в инструкцию vgf2p8affineqb в случае её доступности.

Ссылки

• Весь код в вместе Malkovsky/galois

• Личная рекомендация по и кодам Рида-Соломона, которые можно найти на гитхабе https://github.com/catid/leopard

• Просто отдельное спасибо за наводку по bitreverse

• Репозиторий с построением расширений https://github.com/robdockins/large-gf

• Все 30 неприводимых многочленов степени 8 над и соответствующие примитивные элементы

---

Друзья и коллеги! С удовольствием хотел бы прорекламировать CS Space — открытый научный клуб по CS-related темам; идейных последователей питерского Computer Science Club (и CS Center), расформировавшегося после известных событий. Ребята организуют крутые лекции и курсы по CS от профессионалов своего дела, да еще и помогают мне с написанием научно-популярных статей!

Сайт сообщества: csspace.io
Telegram-канал: t.me/csspace

Если вам понравилась статья — поставьте плюс, автору всегда приятно когда его работу ценят. Возможно вас также заинтересует мой канал А зачем это нужно? где я рассказываю о том, что математику и алгоритмы придумали не только для собеседований в бигтехи.