Кpиптогpафия от папиpуса до компьютеpа




Рекуррентные двоичные последовательности - часть 2


 

+

0

1

*

0

1

 

0

0

1

0

0

0

 

1

1

0

1

0

1

На ЭВМ такому сложению соответствует операция XOR, уже известная нам по машинному шифру ручной замены, а умножению - операция AND. Это поле обладает замечательным свойством - операция вычитания в нем тождественна операции сложения и в записях не употребляется. Поля бит, как байт или слово, можно представить векторами, каждая компонента которых принимает значения из GF(2). Такие вектора удобно рассматривать как многочлены. Байт, например, можно представить многочленом седьмой степени, каждый член которого соответствует одному ненулевому биту в байте:

         (10010101 )=x**7+x**4+x**2+1

Представление битовых полей данных в ЭВМ многочленами упрощает рассмотрение операции их сдвига. Сдвигу данных влево на один бит соответствует умножение многочлена на х, а вправо - деление на х.
     Совокупность всех многочленов степени меньше n представляет собой векторное пространство размерности n над GF(2), так как многочлены можно складывать, вычитать или умножать на константу.
     Теперь, фиксировав неразрешимый над GF(2) многочлен f(x) степени n+1, рассмотрим остатки от деления на него других многочленов. Их множество совпадает с множеством многочленов степени не больше n. Например, f(x)=x**2+x+1 над GF(2) неприводим, потому что f(0)=1 и f(1)=1. Для него остатками будут элементы {0, 1, х, х+1}. На множестве этих остатков можно задать арифметические операции сложения и умножения, рассматривая остатки от деления на многочлен f(x). Легко проверить, что определенные таким образом сложение и умножение обладают всеми необходимыми свойствами обычных арифметических операций: коммутативностью, ассоциативностью и дистрибутивностью. Результат сложения или умножения над двумя элементами из приведенного множества тоже ему принадлежит. И, наконец, в множестве определены О и 1 так, что для произвольного элемента х имеем 0+х=х и 1*х=х. Таким образом, получено GF(4) - расширение поля GF(2) присоединением к нему остатков от деления произвольных многочленов на неприводимый над ним многочлен х**2+х+1. Выбирая разные неприводимые многочлены, можно получать разные расширения GF(2).
     Из школьного курса математики известно, что над полем комплексных чисел любой многочлен разложим на линейные множители или, что то же самое, имеет столько корней, какова его степень. Однако это не так для других полей - в полях действительных или рациональных чисел многочлен х**2+х+1 корней не имеет и не может быть разложен на линейные множители. Аналогично, в поле GF(2) многочлен х**2+х+1 тоже не имеет корней, что просто проверить непосредственно: 1*1+1+1=1 и 0*0+0+1 =1. Тем не менее у f(x)=x**2+x+1 в поле Галуа GF(4) существует корень х, соответствующий многочлену х из таблиц выше, так как f(x)= х**2 +х+1 по модулю f(x).
     Элементы поля Галуа GF(2**N) относительно умножения образуют абелеву группу, то есть на этом множестве для любых его элементов х, у и z выполняются аксиомы:
         x*y=y*x*x*(y*z)=(x*y)*zx*1=1*xx*1/x=1/x*x=1




Содержание  Назад  Вперед