Криптография и шифрование

Криптография > Псевдослучайные последовательности > Рекуррентные двоичные > Теорема 4

Теорема 4

ТЕОРЕМА 4. Многочлен х**k-1 делит х**M-1 в том и только в том случае, если k делит M.

Это вытекает из того факта, что если все корни х**k-1 являются также и корнями х**m-1, то m должно делиться на k.

Теперь обратимся к использованию полиномов в практике вычислений на ЭВМ, широко распространено и легко реализуется программно. Рассмотрим электронную схему деления данных в поле из N бит на полином:

            f(x) = C0+C1*x+...+ Cn*х**N 


      N  N-1               3  2   1
         --¬ --¬          --¬--¬ --¬
  ------>+++>+++----->----++++++>+++------¬
  ¦      LT- LT-          LT-LT- L+-      ¦
  L-T---T-+-T-+-T---------T+-T+-T-+-<------
    L---+---+---+---------+--+--+----

 --¬
 ¦+¦ сумматор XOR
 L--
 --¬
 ¦ ¦ регистр сдвига
 L--

На схеме биты показаны квадратными клетками. Шаг процедуры деления состоит в сдвиге данных влево на один бит и дозаписи освобождающегося крайнего правого бита суммой значений бит по модулю 2, умноженных на соответствующие коэффициенты многочлена f(x), то есть не все ячейки сдвига соединены с относящимися к ним сумматорами. В результате последовательного выполнения отдельных шагов деления исходных данных а(х), справа в данные дозаписывается последовательность s(x), которая выражается формулой:

             s(x)=a(x)/f(x)=S0+S1*x+S2*x**2+...

справедливость которой просто проверить, приравнивая коэффициенты при х в уравнении s(x)*f(x)=a(x). Таким образом, получена связь между линейными рекуррентными последовательностями, делением многочленов над GF(2) и алгоритмом реализации деления на ЭВМ. Например, пусть имеем над GF(2) рекуррентное соотношение Gi+G(i-1)+G(i-3)=0. Многочлен, который ему отвечает, равен 1+х+х**3. Это неприводимый многочлен над GF(2), который порождает расширение GF(8). Мультипликативная группа в GF(8) имеет 7 элементов и циклична в силу простоты числа 7. Электронная схема этого рекуррентного генератора представляется так:

                3   2     1
                         --¬
            ------>------+++-------¬
            ¦            LT-       ¦
            ¦  ---T----T--+--¬     ¦
            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,

или пятое, а через сто лет в 1883 году русский самоучка Первушин нашел уже шестое число Мерсенна, равное:

    2**61-1 =2305843009213693951.

Самое большое известное сейчас простое число - так называемое 32-е число Мерсенна, найденное лишь в 1992 году. Его запись содержит 227832 десятичные цифры или примерно сто страниц текста.