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



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


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

Это вытекает из того факта, что если все корни х**k-1 являются также и корнями х**m-1, то m должно делиться на k.
     Теперь обратимся к использованию полиномов в практике вычислений на ЭВМ, широко распространено и легко реализуется программно. Рассмотрим электронную схему деления данных в поле из N бит на полином:
         f(x) = C0+C1*x+...+ Cn*х**N

На схеме биты показаны квадратными клетками. Шаг процедуры деления состоит в сдвиге данных влево на один бит и дозаписи освобождающегося крайнего правого бита суммой значений бит по модулю 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--+--¬      ¦




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