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




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


L--+--+----+-----<------

Он будет генерировать следующие последовательности при разных начальных данных (периоды в скобках):

000

=>

(0)

001

=>

(0011101)

010

=>

(0100111)

O11

=>

(0111010)

100

=>

(1001110)

101

=>

(1010011)

110

=>

(1101001)

111

=>

(1110100)

Рассмотрим теперь программную процедуру, реализующую деление на примитивный неприводимый многочлен х**3+х+1 в поле Галуа GF(8), представленную короткой программой на языке Бейсик. Переменные в ней рассматриваются как целые числа.

     'программа деления на многочлен х**З+х+1
     DEFINT A-Z
     n = 1
     DO
     m = О

     '-----------расчет бита переноса
     IF n AND 2^2 THEN m = m+1
     IF n AND 2^0 THEN m = m + 1
     n = 2 * (n AND (2^2-1)) OR (m AND 1)
     LOOP UNTIL n = 1
     END

В этой программе сдвиг влево заменен операцией умножения на 2, а бит переноса рассчитывается тестированием бит, соответствующих ненулевым коэффициентам многочлена. В соответствии с теорией период такого генератора составляет 7 и включает в себя все ненулевые числа из 3 бит. Из этой программы видно, что реализация процедуры деления многочленов на ЭВМ или, что то же самое, генерации рекуррентных последовательностей проста.
     Особый интерес для генерации длинных последовательностей представляют элементы GF(2**N), имеющие порядок равный 2**N-1. Они называются примитивными, потому что, возводя их в степень, можно получить весь набор ненулевых элементов поля Галуа. Если 2**N-1 простое число, то все элементы мультипликативной группы (кроме 1, конечно!) примитивны. Однако такие числа, называемые простыми числами Мерсенна, расположены редко. Они с давних пор слыли чемпионами среди простых чисел по своему размеру. Во время Эйлера наибольшим простым числом было:

     2**31-1 =2147483647,




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