поле галуа для чайников

Поле Галуа на Scala

Введение

В этой статье будет рассмотрена тема построения и работы с конечными полями (или полями Галуа), которые используются в криптографии, теории информации и кодирования и других науках, т.е. имеют широкое практическое применение. Сухую теорию о группах/кольцах/полях можно прочитать по ссылке Поля Галуа, а здесь будет больше практики и реализации на языке Scala.

Типы и ограничения

Для начала следует обсудить технические проблемы связанные с представлением полиномов в памяти, с учетом размеров типа Int в языке Scala. Требования сформулированы в списке ниже.

Реализация

Сначала опишем класс Polynomial, который реализует полином и 4 операции. Этот вид полинома является «полуфабрикатом» и не привязан к конечному полю.

Далее абстрактный класс FiniteField, который будет родителем полей Галуа. Внутри FiniteField содержится внутренний класс FiniteFieldPolynomial, такая структура позволяет обеспечить безопасность при проведении операций.

Безопасность заключается в том, что операции возможно производить только с полиномами из одного поля.

Обратите внимание на член modulo, это модуль (или же неприводимый полином) степени поля.

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

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

Иными словами, неприводимыые полиномы играют ту же роль во множествах полиномов, что и простые числа во множествах целых чисел.

Упрощенный код для нахождения множества неприводимых полиномов представлен ниже. Алгоритм следующий:

Осталось реализовать конкретный класс-наследник FiniteField, который будет готовым конечным полем.

Результат умножения может «вылезти» за рамки поля, поэтому иногда надо делить результат на модуль поля. Заметьте как реализовано деление, оно есть умножение a на мультипликативную инверсию b.

В свою очередь инверсия находится с помощью деления, определенного в классе Polynomial.

Вывод

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

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

Полный код приложения можно найти на github’е.

Источник

Арифметика полей Галуа для кодирования информации кодами Рида-Соломона

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

На хабре есть пост посвященный кодированию информации кодами Рида-Соломона, но для примера автор использует простое поле Галуа. В данной статье описывается работа с расширенными полями Галуа, в частности GF(2^m), которые рационально использовать для цифровой информации. С моей аналогичной реализацией кодирования, декодирования, исправления ошибки можно ознакомится здесь.

При работе с кодами Рида-Соломона процент избыточных символов в 2 раза больше восстанавливаемого объема данных. Объясню на примере: если мы имеем последовательность из 10 символов и хотим иметь возможность восстановить ошибки в 3-ех из них (30% исходной информации), то нам нужно хранить 10+3*2=16 символов. Назовем каждую переменную: n = 10, количество информационных символов; f = 3, количество восстанавливаемых символов; g = 16, длина закодированной последовательности. Таким образом, формулу можно записать так: g = n + f * 2.

Поля Галуа

Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа. Таким образом, результат любой операции также является элементом данного поля. Конкретное поле Галуа состоит из фиксированного диапазона чисел. Характеристикой поля называют некоторое простое число p. Порядок поля, т.е. количество его элементов, является некоторой натуральной степенью характеристики pm, где m∈N. При m=1 поле называется простым. В случаях, когда m>1, для образования поля необходим еще порождающий полином степени m, такое поле называется расширенным. GF(p^m) – обозначение поля Галуа.

Для работы с цифровыми данными естественно использовать p=2 в качестве характеристики поля. При m=1 элементом кодовой последовательности будет бит, при m=8 – 8 бит, то есть байт. Собственно коды Рида-Соломона работающие с байтами и являются наиболее распространенными.

Перед тем как переходить к операциям кодирования и декодирования разберемся с арифметикой полей Галуа на примере GF(2^3). Данное поле состоит из чисел от 0 до 7.

Операция сложения

Самой простой является операция сложения, которая является простым побитовым сложение по модулю 2 (ХОR).

Операция умножения

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

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

Перемножим два числа в полиномиальной форме:
5∙7=(x^2+1)∙(x^2+x+1)=x^4+x^3+x^2+x^2+x+1=x^4+x^3+x+1=11011=27

Итак, во-первых, следует заметить, что даже в полиномиальной форме осуществляется сложение по модулю 2, поэтому x^2+x^2=0. Во-вторых, результат умножения 27 не входит в используемое поле GF(2^3) (оно же состоит из чисел от 0 до 7, как было сказано выше). Чтобы бороться с этой проблемой, необходимо использовать порождающий полином. Порождающий полином является неприводимым, то есть простым (по аналогии с простыми числами делится без остатка на 1 и на самого себя). В арифметике полей Галуа неприводимым полиномом является аналог простых чисел. Используем для примера порождающий полином f(x)=x^3+x+1.

Также предполагается, что x удовлетворяет уравнению f(x)=x^3+x+1=0

Вернемся к примеру с умножением:

Составим таблицу умножения:

Операция деления

Операцию деления в полиномиальной форме понять, возможно, но достаточно тяжело. Поэтому гораздо лучше осуществлять его по таблице умножения.

Большое значение имеет таблица степеней элементов поля Галуа. Возведение в степень также осуществляется в полиномиальной форме, аналогично умножению.

Таким образом, составим таблицу степеней:

Таблица степеней обладает цикличностью: седьмая степень соответствует нулевой, значит восьмая соответствует первой и т.д. При желании можно это проверить.

В полях Галуа существует понятие примитивного члена – элемент поля, чьи степени содержать все ненулевые элементы поля. Просмотрев таблицу степеней видно, что этому условию соответствуют все элементы (ну кроме 1 естественно). Однако это выполняется не всегда, для примера приведу таблицу степеней для GF(16).

Для полей, которые мы рассматриваем, то есть с характеристикой 2, в качестве примитивного члена всегда выбирают 2. Учитывая его свойство, любой элемент поля можно выразить через степень примитивного члена.
Пример: 5=26, 7=25

Воспользовавшись этим свойством, и учитывая цикличность таблицы степеней, попробуем снова перемножить числа:
5∙7=2^6∙2^5=2^(6+5)=2^11=2^(11 mod 7)=2^4=6
Результат совпал с тем, что мы вычислили раньше.

А теперь выполним деление:
6÷5=2^4÷2^6=2^(4-6)=2^(-2)=2^((-2)mod 7)=2^5=7
Полученный результат тоже соответствует действительности.

Ну и для полноты картины посмотрим на возведение в степень:
5^2=(〖2^6)〗^2=2^(6∙2)=2^12=2^(12 mod 7)=2^5=7
Опять неожиданно получился такой же результат.

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

Источник

Программная реализация умножения в полях Галуа

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

Итак, я отвлёкся. В детстве-юношестве для помехоустойчивого кодирования можно было бы применить контроль чётности по матричному методу, но сейчас это не серьёзно. Полистав интернет я решил остановиться на кодировании по методу Рида-Соломона. Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент. В этой статье о самих кодах Рида-Соломона я не буду сильно распространяться – это за меня на Хабре сделали много раз и много кто. Здесь я хочу описать реализацию алгоритма умножения в GF[256]. Тем не менее, чтобы не заставлять читателя прыгать по ссылкам, кратенько опишу зачем вообще приходится иметь дело с полями Галуа.

Избыточное кодирование Рида-Соломона это о матрицах. Мы используем матрицы при кодировании и при декодировании. В этих процессах присутствуют как операции умножения матриц, так и операции нахождения обратных матриц — деления. Деление здесь требуется не приблизительное-целочисленное, а самое настоящее, точное. А точное деление для компьютера нерешаемая задача: один разделить на три это ноль целых и бесконечное количество троек после запятой, но память при этом 640 килобайт хватит каждому.

Галуа жил в начале 19 века, жил очень мало (21 год, вообще про его личность история интересная, но сейчас не об этом). Его работы очень сильно пригодились при цифровом кодировании. Конечное поле Галуа — это набор чисел от нуля до n. Суть и интересность этих полей в том, что для элементов этого набора можно определить операции сложения-умножения-вычитания-деления такие, что результат операции будет находиться в самом этом поле. Например, возьмём набор (поле):

в этом поле так же, как и в поле привычных нам, действительных чисел. А вот 5+6 равно не 11, как мы привыкли, а 5+6=3, и это замечательно! 3 входит в это поле (вообще сложение и вычитание для конкретно этого поля это просто побитовый XOR). Для умножения и деления тоже выполняется правило: результат от умножения или деления любых двух чисел из поля (набора… Далее буду говорить только «поле») будет находиться в этом поле.

Вообще, количество элементов поля это число не произвольное. Оно называется «порядком поля» и может быть либо простым числом, либо степенью простого числа (основание этой степени называют «характеристикой поля»). К счастью, количество чисел, которое можно зашифровать с помощью одного байта равно 256, а это два (простое число) в степени 8, и мы можем принять множество всех возможных значений байта за конечное поле Галуа. По умному оно называется GF[256], GF значит Galois Field.

Так вот. Если использовать арифметику в поле Галуа над байтами, то при делении матриц, состоящих из байтов никогда не получится чисел, которые нельзя записать в один байт, а значит то, как реализовывать «в железе» (я использую stm32 в основном) алгоритмы кодирования-декодирования становится немного понятнее.

Немного об арифметике. Сложение и вычитание, как упоминалось ранее, это одна и та же операция в полях Галуа (это точно верно для полей с основанием 2), и реализуется она как побитовый XOR.

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

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

Далее полиномы перемножаются по правилам перемножения полиномов, то есть каждый член в первой скобке умножается на каждый член во второй, но не просто так, а с учётом того, что коэффициент не может быть больше одного.

То есть коэффициенты складываются по модулю 2. Пример умножения в GF[8]:

Далее «складываем» (в кавычках — потому, что по модулю 2) подобные члены, и получаем , что мы переводим в обычное число .

Так как это умножение мы подразумевали в GF[8], то число 10 в результате должно вызвать недоумение: «Как же так? 10 нету в наборе [0,1,2,3,4,5,6,7]». И да. Тут кроется ещё ложка дёгтя. Если получается такая ситуация (результат перемножения не в поле), то далее мы проводим операцию деления по правилам полиномов. Причём делим мы не на что попало, а на определённый, так называемый «порождающий» полином. Откуда он берётся? Почему делится только сам на себя? И прочие вопросы я оставлю без ответа (не потому, что жадный, а потому что не хочу вводить в заблуждение, сам плохо понимаю). Скажу лишь, что для конкретного поля Галуа есть один или несколько таких подходящих порождающих полиномов. Для GF[8] их всего два: 11 и 13, то есть 1011 и 1101 или и

И так, чтобы умножить 6 на 3 в поле GF[8] недостаточно лишь перемножить два многочлена. После перемножения надо результат поделить на один из возможных порождающих многочленов. Здесь мы выберем . Правила деления многочленов столбиком здесь похожи на те, которые мы должны помнить из школьной программы, но во-первых «должны», а во вторых они всё же отличаются. Поясню на нашем примере. Берём старшую степень делимого, в нашем случае это и делим на старшую степень делителя (здесь это также ). Записываем результат 1. Далее получившийся результат умножаем на весь делитель (получается ). Это мы записываем под делимым, и проводим вычитание (а в поле GF[8] вычитание и сложение есть одно и то же) то есть . Сложение проводим по модулю 2, этому нас обязывает работа в поле, и получаем 1. Далее этот результат мы опять бы делили на порождающий многочлен таким же образом, если бы степень получившегося результата (после вычитания) была бы больше или равной степени делителя (порождающего многочлена). А так как степень меньше, то мы за результат деления принимаем остаток от деления, то есть результат вычитания(сложения – здесь это одно и тоже), то есть 1.

Всё. для GF[8] c порождающим полиномом 11.

Казалось бы всё непросто. С такими сложностями нужно много-много кода и суперкомпьютеры и вообще проще хранить таблицу умножения как массив 256х256 (ну или 8х8, смотря какое поле мы используем), Но всё не так плохо. У полей Галуа есть ещё одно замечательное свойство, и связано оно с операцией возведения в степень. Так как возведение в степень — это просто последовательное умножение, то результат возведения в степень так же является элементом поля Галуа. Также для любого поля верно утверждение, что в нём есть минимум один элемент, степени которого содержат в себе всё поле (кроме 0). То есть, если взять для GF[8] число 2, то

Если присмотреться, то можно обратить внимание, что любое число от 1 до 7 можно однозначно представить как 2 в какой либо степени. Так же свойство операции возведения в степень в этом поле таково, что ещё , и так далее. Это значит, что 2 в любой степени может быть представлено в виде двойки в степени от нуля до 6 с помощью операции получения остатка от деления на 7 в случае положительной степени и простой формулы , если показатель — отрицательное число

Собственно, если вспомнить свойство умножения степеней, то умножение чисел многократно упрощается. И чтобы умножить 6 на 3 мы теперь смотрим, в какой степени двойка равна 6 и в какой степени двойка равна 3, складываем степени и смотрим результат — два в какой-то степени, которую можно представть как 2 в степени от 0 до 6 пример:

С делением тоже всё становится предельно понятно:

И вроде бы вот оно! счастье программиста — реализация арифметики в поле Галуа — пара строчек кода, не нужно заморачиваться с полиномами… Да и быстродействие такого кода будет высоким, но тут я столкнулся с ещё одной проблемой: Таблицу степеней двойки в поле GF[8] с порождающим полиномом 11 найти легко. Даже на этом ресурсе есть. А вот таблицу степеней для GF[256] я с нахрапа не нагуглил, так что решил её составить самостоятельно, C# мне в помощь. Пришлось реализовать алгоритм умножения по правилам полиномов.

Привожу рабочую функцию перемножения для GF[2^n] c произвольным полиномом. Ограничение — я испольую 32-битную арифметику, так что n должно быть меньше 16. Также здесь добавлена функция поиска номера старшего бита числа

Теперь, с помощью приведённой выше функции можно составить таблицу степеней двойки для нужного мне GF[256] и написать модуль арифметики Галуа для stm32 с использованием двух таблиц по 256 — одна для прямого, вторая для обратного преобразования числа в его степень. К самой реализации кодирования Рида-Соломона я ещё даже не приступал, но, когда будет готово, думаю поделюсь здесь же. Надеюсь, получится короче.

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Поля Галуа

Структура конечного поля

Существование конечных полей, т.е. полей, состоящих из конечного числа элементов установлено в пункте ☞ ПОЛЕ.

Нет ли противоречий в этих построенных таблицах?

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

Пример. Рассмотрим множество, состоящее из квадратных матрицы второго порядка

Обобщенная теорема Ферма

Пример конечного поля

Ответ. Нет.

Подсказка: см. доказательство теоремы ☞ ЗДЕСЬ.

Пример. Для

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

Доказательства этой теоремы, приведенные в литературе, оказались трудны для моего понимания, поэтому я просто привожу проверку этого утверждения на примере ☞ ЗДЕСЬ.

Полиномы, неприводимые по модулю

В настоящем пункте под неприводимым полиномом понимается нормализованный неприводимый полином.

Непосредственным следствием теоремы 2 является

Доказательство (и критерий, часто позволяющий быстро отыскать такие корни) ☞ ЗДЕСЬ.

Полиномы над GF(2)

Заметим, что любой (не тождественно нулевой) полином из такого поля всегда нормализован.

Вывод. Поле Галуа одновременно обладает свойствами циклической группы, линейного пространства и алгебраического уравнения с целыми коэффициентами. С одной стороны, все ненулевые элементы поля можно представить как степени одного единственного. С другой стороны, операция сложения полиномов эквивалентна сложению векторов, составленных из их коэффициентов. Заметим, что в линейном пространстве не вводится аналога умножения векторов — такого, чтобы при умножении двух векторов получался снова вектор. С третьей стороны, все элементы поля разбиваются на подмножества, каждому из которых соответствует неприводимое алгебраическое уравнение — говорят, что элементы поля являются корнями неприводимых над GF(2) полиномов.

Решение ☞ ЗДЕСЬ.

Решение ☞ ЗДЕСЬ.

Полиномы над GF(p)

Источники

[1]. Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ. 1934.

[2]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

[3]. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.Мир. 1988.

[4]. Ротман Т. Короткая жизнь Эвариста Галуа. Scientific American. N 1, 1983, cc. 84-93. Текст ☞ ЗДЕСЬ.

Источник