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



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


Если рассмотреть степени произвольного элемента х из GF(2**N), то обнаружим, что они образуют абелеву подгруппу. Такие подгруппы принято именовать циклическими. Число элементов этой подгруппы называют порядком элемента х. Из такого определения порядка следует, что если многочлен р(х) принадлежит GF(2**N) и имеет порядок k, то р(х)**K=1. Разберем теперь несколько важных свойств, касающихся порядка элементов в GF(2 ), изложенных в виде теорем.

ТЕОРЕМА 1. Если f(x) - неприводимый многочлен над GF(2), то выполняется равенство f(x**2)=f(x)**2.

Это равенство доказывается тем, что все попарные произведения в f(x)**2 равны нулю над GF(2). Например, (х**2+х+1)**2=х**4+x**2+1.

ТЕОРЕМА 2. Если неприводимый многочлен f(x) над GF(2**N) имеет порядок k, то k делит 2**N-1.

Это следует из теоремы Лагранжа, утверждающей, что число элементов группы G делится на число элементов любой своей подгруппы Н. Подгруппа Н расслаивает группу G на смежные классы элементов, не пересекающиеся меж собой. Так, элементы х и у считаются принадлежащими одному классу по подгруппе Н, если у/х принадлежит Н. Поскольку классы не пересекаются и содержат одинаковое число элементов, то число элементов группы делится на число элементов в подгруппе. Из теоремы 2 вытекает важное следствие, что если 2**N-1 простое число, то мультипликативная группа GF(2**N) циклическая и порядок любого ее неединичного элемента тоже равен 2**N-1.

ТЕОРЕМА 3. Любой многочлен р(х) из GF(2**N) удовлетворяет уравнению х**k=х, где К=2**N.

Порядок ненулевого р(х) делит 2**N-1 и имеем х**(K-1)=1, а так как для р(х)=0 имеем уравнение х=0, то в результате любой р(х) удовлетворяет уравнению х**K=х.
     Отметим особое положение уравнения х**K=х, где К=2**N , поскольку его корни порождают все элементы поля GF(2 ). Так как уравнение х**(K-1)-х=0 имеет корнем х=0, то, разделив его на х, получаем уравнение х**(K-1)-1=0, все корни которого ненулевые. Производная уравнения имеет вид (x**k-x)=2*N*x**(n-1)-1=1, и у нее нет общих корней с исходным уравнением. Следовательно, в этом уравнении все корни различны, и так как их число равно 2**n, то они совпадают со всеми элементами поля GF(2).




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