Найти значение заданного выражения в поле галуа
Обновлено: 21.11.2024
Если хочется сделать передачу или хранение данных более надёжными, применив к ним избыточное кодирование, то для этого неплохо подойдёт код Рида-Соломона. Понимаю, что на эту тему написано немало материала, тем не менее ориентирован он, как правило, на людей неплохо подготовленных в математике. Если просто хочется реализовать такой алгоритм в каком-нибудь проекте, не сильно углубляясь в математику, то надеюсь этот материал будет весьма полезным.
Арифметика в поле Галуа GF[256]
Напомню. В нашей привычной арифметике результатом операции деления может оказаться дробное число вроде (1/3). В десятичном представлении это 0,3333333… и так далее. Такие числа не очень удобны для компьютерных вычислений, так что для кодирования информации решили применить давно придуманные поля Галуа. Здесь числа это такие же привычные нам числа, только их количество – это строго определённая величина. Для кодирования хорошо подходит поле GF[256] (Galois Field 256 – поле Галуа, содержащее 256 элементов), То есть вместо всех привычных значений от до , с вообще всеми возможными промежуточными, включая , , 42, а также гугол и прочие, у нас есть 256 чисел: 0, 1, 2… 255. Всё. Никаких тебе 7092, 3,15 и 2/3. Только числа из списка. (42 — в списке. Без паники).
Но просто так числа ничего не дают. Вся их польза – это операции. Их можно складывать, вычитать, делить и умножать, только это не просто так сложил-вычел. Результат сложения-вычитания-деления-умножения есть число также от 0 до 255. Какое это число? Два плюс два равно сколько? Так вот, ни разу не 4. 2+2=0. Вообще, сложение в GF[256] работает также, как и вычитание. это побитовое исключающее «или» – XOR. Умножение-деление — там другие правила, но на простейшем уровне можно считать, что это таблицы. Так как чисел ограниченное количество, то можно составить всеобъемлющую таблицу умножения. Каким образом? Совсем детально здесь не буду распространяться. Про умножение – подробно писал в предыдущей статье, деление и возведение в степень проще всего реализовать используя таблицы степеней и логарифмов. Да, умножение тоже можно реализовать с помощью логарифмов, так эта операция выполняется быстрее.
Для начала нужно составить таблицы степеней и логарифмов примитивного члена. Здесь надо напомнить (рассказать) про свойство возведения в степень в поле Галуа. Если последовательно умножать (по правилам поля, конечно) двойку: , то начиная со степени 255 результат начнёт повторяться, то есть и также . Если упорно продолжить умножать дальше, пока есть терпение и деньги на зарплату эмигрантам, то результат будет такой:
и так далее. Значения, если использовать порождающий полином 285 (о нём было в предыдущей статье сейчас это не сильно важно), такие:
Также в промежутке от до включительно нет ни одного повторяющегося результата. А это значит, что любое число (кроме нуля) из поля GF[256] можно записать как два в какой-нибудь степени. И что из этого? А вот что. Правила умножения и деления степеней здесь выполняются. То есть
а также . Это вместе значит, что не надо заморачиваться и реализовывать алгоритмы умножения и деления по сложным правилам, достаточно лишь узнать в какой степени двойка для каждого множителя (логарифм) и сложить или вычесть степени чтобы произвести операции умножения или деления. Пример:
Возведение в степень и нахождение логарифма – просто обращение к массивам, в которых по 256 элементов (так как , для таблицы степеней достаточно 255 элементов).
Теперь нужно сделать пару важных оговорок для тех, кто захочет самостоятельно реализовать алгоритмы исходя из описания. (Когда я изучал вопрос, везде эти вещи считались «очевидными» со всеми вытекающими)
- Во-первых: В примере выше мы возводили в степень число 2. Для числа 2 выполняется правило об уникальности степеней от 0 до 254. Не для каждого числа поля это верно. Те числа, для которых это верно – это примитивные члены поля. Часто в литературе обозначают как . При кодировании Рида-Соломона число неоднократно вспоминают и используют. Хотя его выбор не влияет на арифметику, результат кодирования будет отличаться в зависимости от выбора.
- Во-вторых: Когда мы говорим о сложении и вычитании степеней при умножении и делении, то речь идёт не о сложении и вычитании по правилам поля Галуа. Здесь это просто сложение и вычитание. Могут получиться как отрицательные значения, так и числа больше 255 результат при этом легко найти, помня о том, что степени повторяются через каждые 255 значений, то есть, например, степень 257 равна степени 2, а степень -1 равна степени 254.
И так, мы построили свою арифметику. С целыми числами и делением без остатка. Для простоты использования чисел GF[256] можно создать класс и в нём переопределить операции сложения, вычитания, деления и умножения. Так дальнейший код будет немного короче.
Полиномы
Операции с полиномами
Сложение полиномов
Для того чтобы сложить два полинома мы просто складываем коэффициенты при одинаковых степенях по правилам поля Галуа. Всё. Пример: выполняем следующую операцию:
Для программной реализации (и для кодирования) лучше записать полиномы так, чтобы они были одной длины и с явным указанием степеней:
В результате имеем:
Так как в поле GF[256] вычитание эквивалентно сложению то пишу только знак "+". Вычитание полиномов также эквивалентно сложению полиномов.
Умножение полиномов
При умножении каждый член одного полинома умножается на каждый член второго. Результат складывается:
Когда мы перемножаем и складываем коэффициенты — мы используем правила умножения и сложения поля Галуа GF[256]. Сложение степеней — это обычное сложение, то есть:
Деление полиномов
С делением всё немного сложнее, но тоже ничего сверхъестественного. Это как деление столбиком, только с полиномами. Берём старший член делимого и старший делителя. Делим, записываем результат. Полученное умножаем на делитель и вычитаем (прибавляем – в поле Галуа неважно) из делимого. Далее результат вычитания делим также, как делили изначально. Всё повторяется до тех пор, пока старшая степень остатка больше или равна старшей степени делителя.
Нужно разделить на . Записываем в столбик. Затем делим старшие члены: на (деление по правилам поля Галуа, вычитание степени — обычное). Результат записываем.
Теперь умножаем на . Получаем записываем это под делимым и складываем. Результат сложения также записываем под чертой (это остаток)
Теперь остаток также делим на делитель. (Делим старшие члены) умножаем — вычитаем — всё как на первом шаге:
В остатке теперь старший член – это . Степень меньше, чем у старшего члена делителя () – значит всё, деление закончено. Частное это , остаток .
И какой толк от всех этих ваших полиномов? В принципе без алгоритмов кодирования-декодирования Рида-Соломона я не знаю как их с пользой применить. Слышал краем уха, что они также применяются при шифровании информации. Непосредственно как кодировать и декодировать по методу Рида-Соломона напишу в следующей статье, а пока, благодарю за внимание!
Читайте также: