Полиномиальная арифметика и поля Галуа, или Информация, воскресшая из пепла II

Крис Касперски

Искусство рассуждать – это искусство обманывать самого себя

Антуан де Сент-Экзюпери «Цитадель»

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

Полиномиальная арифметика

Полиномиальной арифметике посвящен шестой раздел третьего тома «Искусства программирования» Дональда Кнута, где полиному дается следующее определение: «Формально говоря, полином над S представляет собой выражение вида: u(x) = u_nxⁿ + … + u₁x + u₀ , где коэффициенты u_n , … , u₁ , u₀ – элементы некоторой алгебраической системы S, а переменная x может рассматриваться как формальный символ без определяющего значения. Будем полагать, что алгебраическая система S представляет собой коммутативное кольцо с единицей. Это означает, что S допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативными и коммутативными бинарными операциями, определенными на S, причем умножение дистрибьютивно по отношению к сложению. Существует также единичный элемент по сложению 0 и единичный элемент по умножению 1, такие, что a + 0 == a и a * 1 == a для всех a из S. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как операции, обратной по отношению к умножению, ничего не предполагается. Полином 0x^n + m + … + 0x ^n + 1 +  u_nxⁿ + … + u₁x + u₀ рассматриваетсякак идентичный u_nxⁿ + … + u₁x + u₀ , хотя формально он отличается от него».

Таким образом, вместо того, чтобы представлять информационное слово D, кодовое слово C и остаток от деления R в виде целых чисел (как это делалось нами ранее), мы можем связать их с соответствующими коэффициентами двоичного полинома, выполняя все последующие математические манипуляции по правилам полиномиальной арифметики. Выигрыш от такого преобразования на первый взгляд далеко не очевиден, но не будем спешить, а лучше преобразуем любое пришедшее нам в голову число (например, 69h) в двоичный полином. Запустив «Калькулятор» или любое другое подходящее приложение по вашему вкусу, переведем наше число в двоичный вид (при соответствующих навыках эту операцию можно выполнить и в уме, см. «Техника и философия хакерских атак» Криса Касперски): 69h –> 1101001.