Что такое конечное поле
Конечное поле GF(256) и немного магии
Введение
Будучи студентом я посещаю занятия по криптографии. И разумеется этот курс не мог обойти вниманием стандарт AES.
При реализации данного алгоритма встает вопрос о реализации полей GF(2^8), что будет освещено в данной статье. Будут рассмотрены: битовая магия для умножения элементов поля, шаблоны для генерации таблиц замен на этапе компиляции.
Вторая часть предполагает, что читатель имеет доступ к компилятору с поддержкой C++14. Первая часть будет написана в стиле Си.
Сперва рассмотрим как образуется поле с простым числом элементов GF(p).
Его элементы — числа 
. Операции сложения и умножения — сложение и умножение по модулю p.
2 + 6 = 8%7 = 1
4 * 3 = 12%7 = 5
На основе полей GF(p) строятся более общие поля GF(p^q), p — простое, q — натуральное.
Элементы таких полей — многочлены над полем GF(p):
Сложение в данном поле будет непосредственно сложением данных многочленов.
Например при p=2, q=3:
С умножением чуть сложнее. Для того что бы определить его требуется многочлен Q(x) степени q, неприводимый над GF(p) (не существует двух многочленов меньшей степени, в произведении дающих данный). К счастью для любых p и q такой многочлен существует.
Когда многочлен Q(x) выбран, для того что бы найти произведение двух элементов a*b поля нужно:
Q(x) = x^3 + x + 1 (Неприводимый многочлен)
a = x^2 + 1, b = x^2
a(x) * b(x) = x^4 + x^2
(x^4 + x^2) % Q(x) = (x^4 + x^2 — x*Q(x)) % Q(x) = (x^3 + x) % Q(x) = (x^3 + x — Q(x)) % Q(x) = 1 = a * b
Q(x) = x^2 + x + 2 (Неприводимый многочлен)
a = x+2
b = 2x + 2
a(x) * b(x) = 2x^2 + (6%3) * x + (4%3) = 2x^2 + 1
(2x^2 + 1) % Q(x) = (2x^2 + 1 — 2Q(x)) % Q(x) = ((-2%3)x + (-3%3)) % Q(x) = x % Q(x) = x
Реализация
Итак, требуется реализовать следующие операции в поле GF(256) над многочленом x^8 + x^4 + x^3 + x + 1:
Первое что приходит на ум — реализовать произведение многочленов наивным алгоритмом:
После чего написать функцию нахождения остатка от деления на многочлен.
В этот момент я задумался что будет дальше. А дальше меня ждал расширенный алгоритм Евклида для многочленов, и хоть на самом деле это не так страшно, было решено подумать. А нельзя ли сделать это как-нибудь красиво? Жаль нельзя используя одну операцию перемножить два таких многочлена, найти остаток от деления на другой.
А точно ли нельзя? Посмотрим что нам мешает реализовать произведение многочленов через простое произведение.
По формуле для произведения многочленов имеем:
Для произведения двух чисел в двоичной системе счисление получаем почти аналогиное выражение:
Разница состоит в том, что для многочленов выражение определяет коэффициент при .
Аналогичное высказывание для чисел не будет верно из-за того, что в предыдущем разряде могло произойти переполнение, меняющее значение рассматриваемого.
Как избавиться от переполнения? Очень просто. Рассмотрим следующую запись:
Поскольку при перемножении многочленов степени не выше 7 нельзя получить многочлен степени выше 14, разряду будет соответствовать сумма не более чем из 15 нулей и единиц (на самом деле легко убедиться что не более 8), а значит переполнение невозможно. Остается только преобразовать непосредственную сумму в сумму по модулю 2, выделив младший бит.
И так, если представлять полином как число, в котором каждому блоку соответствует блок из 4 бит, то произведение можно написать следующим образом:
Теперь разберем произведение как элементов поля Галуа.
Посмотрим на полином . В выбранном представлении он выглядит как q = 0x100011011. Невооруженным глазом видно большое количество нулевых блоков сразу после старшего блока. При умножении Q(x) на полином вида мы получим полином:
или полином, старшие блоки которого есть . Этим мы и воспользуемся для написания функции умножения:
С умножением разобрались. Теперь нужно научиться находить обратный элемент по нему.
Вспоминаем, что поле без сложения и 0 образует группу из 255 элементов. Отсюда получаем, что для любого элемента x найдется число r, равное размеру подгруппы, образованной этим элементом, такое что x^r = 1. Так как порядок подгруппы — делитель порядка группы, , что с свою очередь дает нам что . Тогда согласно определению обратного элемента имеем :
Все? Ах, да, нужно уметь преобразовывать исходные байты в расширенную форму, в которой мы проводим все операции. Это можно сделать в лоб циклом, но не сегодня. Внутренний голос говорит что нужно использовать грязный трюк. В конце концов не я ли читал статью Обстоятельно о подсчёте единичных битов?
Обозначим байт как 0bABCDEFGH. Первое что приходит в голову это умножение на 0b1001001 трех младших бит:
0bFGH * 0b1001001 = 0bFGHFGHFGH
0bFGHFGHFGH | 0b100010001 = 0bF000G000H, или три младших бита встали на свои места.
Аналогично проделывается над средней тройкой бит и старшей парой. Трюк был придуман. Но три умножения это как то слишком много. Нельзя ли делать тоже самое в раз по 4 бита? Рассмотрев многочисленные выборки бит я сумел найти лишь одну четверку с которой это работает:
Обратите внимание на младшие биты 7, 6, 1, 0 блоков. Для них характерны наличие нужного бита на своем месте и что не менее важно, невозможность переполнения за счет младших (относительно данных) бит.
Как было сказано, двух парных четверок бит я не нашел. Неудача? Не совсем. Если мы способны поставить семь из восьми бит на свои места использовав 2 умножения, мы можем поставить все 8, водрузив последний на свое место простым сдвигом.
С сжатием обратно дела обстоят проще. Следующее умножение показывает как сжать 4 бита:
С учетом этого код приобретает следующий вид:
Пусть считает компилятор
Зачем использовать довольно дорогие преобразования байт когда можно воспользоваться просчитанной заранее таблицей? В данной секции я поясню как просчитать её на этапе компиляции при помощи магии шаблонов на примере таблицы обратных элементов по сложению.
Первым делом всем ранее написанным функциям добавим спецификатор constexpr (с этого момента компиляция потребует поддержки с++14). Это позволит использовать данные функции в качестве аргументов шаблонов.
Рассмотрим что происходит при попытке использовать GaloisTable ::data.
Компилятор находит соответствующую специализацию шаблона, в которой data определена как GaloisTable ::data. Она в свою очередь определена через GaloisTable ::data и так далее.
Когда m достигает 0 компилятору удается найти более конкретную специализацию шаблона (А компилятор всегда предпочитает более конкретную). Тут то и завершается рекурсивное задание классов и из последовательности в Data… создается сам массив, заимствованный всеми предыдущими классами.
Data… на это шаге будет ничем иным как inverse(0), inverse(1), …, inverse(255), что нам и было нужно.
Надеюсь, статья была чем-либо полезной.
Update: Префикс Galua заменен на Galois.
Инструменты сайта
Основное
Навигация
Информация
Действия
Содержание
Поля Галуа
Структура конечного поля
Существование конечных полей, т.е. полей, состоящих из конечного числа элементов установлено в пункте ☞ ПОЛЕ.
Нет ли противоречий в этих построенных таблицах?
В самом деле, возможно, что существует не найденная нами цепочка действий, которая приведет к противоречию с каким-то результатом из полученных таблиц. Ответ на этот вопрос оказывается отрицательным: противоречий мы не получим.
Пример. Рассмотрим множество, состоящее из квадратных матрицы второго порядка
Обобщенная теорема Ферма
Пример конечного поля
Ответ. Нет.
Подсказка: см. доказательство теоремы ☞ ЗДЕСЬ.
Пример. Для
Теорема. Конечные поля одинакового порядка изоморфны, т.е. между элементами этих полей можно установить такое взаимно-однозначное соответствие, которое сохраняет результаты сложения и умножения элементов.
Доказательства этой теоремы, приведенные в литературе, оказались трудны для моего понимания, поэтому я просто привожу проверку этого утверждения на примере ☞ ЗДЕСЬ.
Полиномы, неприводимые по модулю
В настоящем пункте под неприводимым полиномом понимается нормализованный неприводимый полином.
Непосредственным следствием теоремы 2 является
Доказательство (и критерий, часто позволяющий быстро отыскать такие корни) ☞ ЗДЕСЬ.
Полиномы над GF(2)
Заметим, что любой (не тождественно нулевой) полином из такого поля всегда нормализован.
Вывод. Поле Галуа одновременно обладает свойствами циклической группы, линейного пространства и алгебраического уравнения с целыми коэффициентами. С одной стороны, все ненулевые элементы поля можно представить как степени одного единственного. С другой стороны, операция сложения полиномов эквивалентна сложению векторов, составленных из их коэффициентов. Заметим, что в линейном пространстве не вводится аналога умножения векторов — такого, чтобы при умножении двух векторов получался снова вектор. С третьей стороны, все элементы поля разбиваются на подмножества, каждому из которых соответствует неприводимое алгебраическое уравнение — говорят, что элементы поля являются корнями неприводимых над GF(2) полиномов.
Решение ☞ ЗДЕСЬ.
Решение ☞ ЗДЕСЬ.
Полиномы над GF(p)
Источники
[1]. Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ. 1934.
[2]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.
[3]. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.Мир. 1988.
[4]. Ротман Т. Короткая жизнь Эвариста Галуа. Scientific American. N 1, 1983, cc. 84-93. Текст ☞ ЗДЕСЬ.
Содержание
Характеристики
Более общая алгебраическая структура, удовлетворяющая всем остальным аксиомам поля, но чье умножение не обязательно должно быть коммутативным, называется делительное кольцо (или иногда тело). К Маленькая теорема Веддерберна, любое конечное тело коммутативно и, следовательно, является конечным полем.
Существование и уникальность
Таким образом, мы имеем следующую классификационную теорему, впервые доказанную в 1893 г. Э. Х. Мур: [1]
Явная конструкция
Непростые поля
грамм F ( q ) = грамм F ( п ) [ Икс ] / ( п ) 
Возможный выбор такого многочлена дается формулой Многочлены Конвея. Они обеспечивают определенную совместимость между представлением поля и представлениями его подполей.
В следующих разделах мы покажем, как описанный выше общий метод построения работает для малых конечных полей.
Поле с четырьмя элементами
Следовательно, для GF (4) конструкция предыдущего раздела должна включать этот многочлен, и
| Добавление | Умножение | Разделение | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
GF (п 2 ) для нечетного простого числа п
GF (8) и GF (27)
GF (16)
куда а, б, c, d либо 0 или же 1 (элементы GF (2) ), и α такой символ, что
Мультипликативная структура
Дискретный логарифм
Логарифмы Зеха полезны для больших вычислений, таких как линейная алгебра над полями среднего размера, то есть полями, которые достаточно велики, чтобы сделать естественные алгоритмы неэффективными, но не слишком большими, так как нужно предварительно вычислить таблицу того же размера, что и порядок поля.
Корни единства
Пример: GF (64)
Поле GF (64) имеет несколько интересных свойств, которые не разделяются полями меньшего размера: у него есть два подполя, ни одно из которых не содержится в другом; не все генераторы (элементы с минимальный многочлен степени 6 над GF (2) ) примитивные элементы; и не все примитивные элементы сопряжены Группа Галуа.
Автоморфизм Фробениуса и теория Галуа
Обозначается φ k то сочинение из φ с собой k раз у нас есть
было бы больше, чем п k корни.
Из того факта, что отображение Фробениуса сюръективно, следует, что каждое конечное поле является идеально.
Полиномиальная факторизация
Как каждый кольцо многочленов над полем уникальная область факторизациикаждый приведенный многочлен над конечным полем может быть факторизован единственным способом (с точностью до порядка множителей) в произведение неприводимых монических многочленов.
Существуют эффективные алгоритмы проверки полиномиальной неприводимости и факторизации многочленов над конечным полем. Они являются ключевым шагом для разложения многочленов на целые числа или рациональное число. По крайней мере, по этой причине каждый система компьютерной алгебры имеет функции для факторизации многочленов над конечными полями или, по крайней мере, над конечными простыми полями.
Неприводимые многочлены заданной степени
Это свойство используется для вычисления произведения неприводимых множителей каждой степени многочленов над GF (п) ; видеть Факторизация четкой степени.
Число монических неприводимых многочленов заданной степени над конечным полем
Номер N(q, п) монических неприводимых многочленов степени п над GF (q) дан кем-то [4]
(Немного более простая) нижняя оценка для N(q, п) является
Приложения
В криптография, сложность задача дискретного логарифмирования в конечных полях или в эллиптические кривые является основой нескольких широко используемых протоколов, таких как Диффи – Хеллмана протокол. Например, в 2014 году безопасное интернет-соединение с Википедией включало протокол Диффи – Хеллмана с эллиптической кривой (ECDHE) над большим конечным полем. [5] В теория кодирования, многие коды строятся как подпространства из векторные пространства над конечными полями.
Конечные поля широко используются в теория чисел, так как многие проблемы с целыми числами можно решить, уменьшив их по модулю один или несколько простые числа. Например, самые быстрые известные алгоритмы для полиномиальная факторизация и линейная алгебра над полем рациональное число продолжаем редукцией по модулю одного или нескольких простых чисел, а затем реконструируем решение с помощью Китайская теорема об остатках, Хензель лифтинг или LLL алгоритм.
Точно так же многие теоретические проблемы теории чисел можно решить, рассматривая их редукцию по модулю некоторых или всех простых чисел. См., Например, Принцип Хассе. Многие недавние разработки алгебраическая геометрия были мотивированы необходимостью расширить возможности этих модульных методов. Доказательство Уайлса Великой теоремы Ферма является примером глубокого результата с использованием множества математических инструментов, включая конечные поля.
В Гипотезы Вейля касаются количества точек на алгебраические многообразия над конечными полями, и теория имеет множество приложений, включая экспоненциальный и сумма символов оценки.
Расширения
Алгебраическое замыкание
Конечное поле F не является алгебраически замкнутым. Чтобы продемонстрировать это, рассмотрим полином
Квазиалгебраическое замыкание
Хотя конечные поля не алгебраически замкнуты, они квазиалгебраически замкнутый, что означает, что каждый однородный многочлен над конечным полем имеет нетривиальный нуль, компоненты которого находятся в поле, если число его переменных больше его степени. Это было предположение Артин и Диксон доказано Chevalley (видеть Теорема Шевалле – Предупреждение).
Маленькая теорема Веддерберна
А делительное кольцо является обобщением поля. Делительные кольца не считаются коммутативными. Некоммутативных конечных тел не бывает: Маленькая теорема Веддерберна заявляет, что все конечные делительные кольца коммутативны, следовательно, конечные поля. Результат сохраняется, даже если мы ослабим ассоциативность и рассмотрим альтернативные кольца, посредством Теорема Артина – Цорна. [9]
Содержание
Характеристики
Более общая алгебраическая структура, удовлетворяющая всем остальным аксиомам поля, но чье умножение не обязательно должно быть коммутативным, называется делительное кольцо (или иногда тело). К Маленькая теорема Веддерберна, любое конечное тело коммутативно и, следовательно, является конечным полем.
Существование и уникальность
Таким образом, мы имеем следующую классификационную теорему, впервые доказанную в 1893 г. Э. Х. Мур: [1]
Явная конструкция
Непростые поля
грамм F ( q ) = грамм F ( п ) [ Икс ] / ( п )
Возможный выбор такого многочлена дается формулой Многочлены Конвея. Они обеспечивают определенную совместимость между представлением поля и представлениями его подполей.
В следующих разделах мы покажем, как описанный выше общий метод построения работает для малых конечных полей.
Поле с четырьмя элементами
Следовательно, для GF (4) конструкция предыдущего раздела должна включать этот многочлен, и
| Добавление | Умножение | Разделение | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
GF (п 2 ) для нечетного простого числа п
GF (8) и GF (27)
GF (16)
куда а, б, c, d либо 0 или же 1 (элементы GF (2) ), и α такой символ, что
Мультипликативная структура
Дискретный логарифм
Логарифмы Зеха полезны для больших вычислений, таких как линейная алгебра над полями среднего размера, то есть полями, которые достаточно велики, чтобы сделать естественные алгоритмы неэффективными, но не слишком большими, так как нужно предварительно вычислить таблицу того же размера, что и порядок поля.
Корни единства
Пример: GF (64)
Поле GF (64) имеет несколько интересных свойств, которые не разделяются полями меньшего размера: у него есть два подполя, ни одно из которых не содержится в другом; не все генераторы (элементы с минимальный многочлен степени 6 над GF (2) ) примитивные элементы; и не все примитивные элементы сопряжены Группа Галуа.
Автоморфизм Фробениуса и теория Галуа
Обозначается φ k то сочинение из φ с собой k раз у нас есть
было бы больше, чем п k корни.
Из того факта, что отображение Фробениуса сюръективно, следует, что каждое конечное поле является идеально.
Полиномиальная факторизация
Как каждый кольцо многочленов над полем уникальная область факторизациикаждый приведенный многочлен над конечным полем может быть факторизован единственным способом (с точностью до порядка множителей) в произведение неприводимых монических многочленов.
Существуют эффективные алгоритмы проверки полиномиальной неприводимости и факторизации многочленов над конечным полем. Они являются ключевым шагом для разложения многочленов на целые числа или рациональное число. По крайней мере, по этой причине каждый система компьютерной алгебры имеет функции для факторизации многочленов над конечными полями или, по крайней мере, над конечными простыми полями.
Неприводимые многочлены заданной степени
Это свойство используется для вычисления произведения неприводимых множителей каждой степени многочленов над GF (п) ; видеть Факторизация четкой степени.
Число монических неприводимых многочленов заданной степени над конечным полем
Номер N(q, п) монических неприводимых многочленов степени п над GF (q) дан кем-то [4]
(Немного более простая) нижняя оценка для N(q, п) является
Приложения
В криптография, сложность задача дискретного логарифмирования в конечных полях или в эллиптические кривые является основой нескольких широко используемых протоколов, таких как Диффи – Хеллмана протокол. Например, в 2014 году безопасное интернет-соединение с Википедией включало протокол Диффи – Хеллмана с эллиптической кривой (ECDHE) над большим конечным полем. [5] В теория кодирования, многие коды строятся как подпространства из векторные пространства над конечными полями.
Конечные поля широко используются в теория чисел, так как многие проблемы с целыми числами можно решить, уменьшив их по модулю один или несколько простые числа. Например, самые быстрые известные алгоритмы для полиномиальная факторизация и линейная алгебра над полем рациональное число продолжаем редукцией по модулю одного или нескольких простых чисел, а затем реконструируем решение с помощью Китайская теорема об остатках, Хензель лифтинг или LLL алгоритм.
Точно так же многие теоретические проблемы теории чисел можно решить, рассматривая их редукцию по модулю некоторых или всех простых чисел. См., Например, Принцип Хассе. Многие недавние разработки алгебраическая геометрия были мотивированы необходимостью расширить возможности этих модульных методов. Доказательство Уайлса Великой теоремы Ферма является примером глубокого результата с использованием множества математических инструментов, включая конечные поля.
В Гипотезы Вейля касаются количества точек на алгебраические многообразия над конечными полями, и теория имеет множество приложений, включая экспоненциальный и сумма символов оценки.
Расширения
Алгебраическое замыкание
Конечное поле F не является алгебраически замкнутым. Чтобы продемонстрировать это, рассмотрим полином
Квазиалгебраическое замыкание
Хотя конечные поля не алгебраически замкнуты, они квазиалгебраически замкнутый, что означает, что каждый однородный многочлен над конечным полем имеет нетривиальный нуль, компоненты которого находятся в поле, если число его переменных больше его степени. Это было предположение Артин и Диксон доказано Chevalley (видеть Теорема Шевалле – Предупреждение).
Маленькая теорема Веддерберна
А делительное кольцо является обобщением поля. Делительные кольца не считаются коммутативными. Некоммутативных конечных тел не бывает: Маленькая теорема Веддерберна заявляет, что все конечные делительные кольца коммутативны, следовательно, конечные поля. Результат сохраняется, даже если мы ослабим ассоциативность и рассмотрим альтернативные кольца, посредством Теорема Артина – Цорна. [9]