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

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

Теорема 3

ТЕОРЕМА 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).