Дискретная математика и криптология

         

Дискретная математика и криптология

Глава 19. ПРИЛОЖЕНИЯ    

Алгоритм шифрования DES  


Алгоритм ГОСТ 28147-89  

Блочный шифр IDEA  

RIJNDAEL  

Математические операции алгоритма  

Описание алгоритма  

Состояния, ключи и число циклов шифрования

Цикловое преобразование  

Ключевое расписание  

Стандарт генерации ключей ANSI Х9.17   

Алгоритм А5/1  

Американский стандарт хэш-функции (SHS)  


Криптосистема RSA  

Шифрсистема Эль Гамаля  

Схема цифровой подписи Эль Гамаля  

Словарь терминов  

Ответы и решения  



Литература  

СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ


Многие криптографические системы используют для шифрования информации псевдослучайные последовательности, генерируемые программным способом. Качество шифрования определяется определёнными свойствами псевдослучайных последовательностей, в частности, их периодами. Так как порождение последовательностей большого периода основано на реализации многократных итераций преобразований, то для криптологии представляет интерес изучение структурных и периодических свойств преобразований конечных множеств.

6.1. Периоды последовательностей

Последовательность элементов множества X назовём последовательностью над X и обозначим X®.

Последовательность

X®={x1,x2,…,xi,…} над X называется периодической с предпериодом N и периодом T, если N+1 и T – наименьшие из натуральных чисел, при которых xi=xi+T

для всех i>N. Заметим, что если для всех i>N в xi=xi+t, то T/t.

Если N=0, то последовательность X®

называется чисто периодической с периодом T.

Утверждение 6.1. Если последовательность Y®={j(xi)} над Y получена с помощью отображения j:Х®Y из периодической последовательности X®={xi}

над Х с предпериодом N и периодом T, то Y® - периодическая с предпериодом N’ и периодом T’, где N’£N, T’ делит T.

Доказательство. Если xi=xi+Т, то и j(xi)=j(xi+Т), следовательно, N’£N и T’/T.       ¨    

Теорема 6.1. Для последовательностей X®={xi} и Y®={yi} над конечной аддитивной группой X, где yi=x1+x2+…+xi,

i=1,2,…, верны утверждения:

1. Если X® - периодическая с предпериодом N>0 и периодом T, то Y®

– периодическая с предпериодом N-1 и периодом T’, где T’/d×T и d есть порядок элемента yN+T-yN

группы X.

2. Если X® - чисто периодическая с периодом T, то Y® – чисто периодическая с периодом T’, где T’/d×T и d

есть порядок элемента yT группы X, при этом yr×d×T=0 при r=1,2,…

Доказательство. Из соотношения между членами последовательностей X® и Y® имеем:

yi+d×T  = yi+xi+1+xi+2+…+xi+d×T.


В условиях утверждения 1 в силу периодичности X® при всех i³N выполнено xi+1+xi+2+…+xi+T=yN+T -yN, и как следствие

yi+d×T = yi+d×(yN+T-yN) = yi.

Значит, N’<N и T’/d×T. Если N’<N-1, то yN-1+d×T=yN-1

и, следовательно, хN-1+d×T=хN-1, что противоречит условию.        

В условиях утверждения 2 порядок d элемента yT совпадает при всех i с порядками элементов xi+1+xi+2+…+xi+T. Поэтому при всех i

выполнено yi+d×T=yi, значит T’/d×T. При натуральных r имеем

yr×d×T = r×d×(x1+x2+…+xT) = r×d×yT = 0.                                           ¨

Рассмотрим  последовательность X® над X=Х1´…´Xп, в которой каждый член состоит из п компонент. Выделим в X® последовательность (над Хj) j-х компонент её членов. Обозначим её Xj® и назовём j-й координатной последовательностью последовательности X®, j=1,2,…,n.

С другой стороны, из последовательностей Xj®={xij} - над Хj, j=1,2,…,n, можно образовать последовательность X®={xi} над Х1´…´Xп, где xi=(xi1,…,xin), i=1,2,… Последовательность X® назовём сопряжением

последовательностей Х1®,…,Xп® (обозначается X®=Х1®*…*Xп®).

Очевидно, любая последовательность X® над X=Х1´…´Xп является сопряжением п координатных последовательностей. Из данных определений следует утверждение.

Утверждение 6.2. Последовательность X® над X=Х1´…´Xп является периодической с предпериодом N и периодом T тогда и только тогда, когда Xj® – периодическая последовательность с предпериодом Nj и периодом Tj, где N=max{N1,…,Nn}, T=НОК(T1,…,Tn).

Теорема 6.2. Если последовательность Y®={j(xi,1,…,xi,n)}

периода T получена с помощью отображения j:Х1´…´Xп®Y из периодических последовательностей Xj®={xij} над Хj с периодами Tj, j=1,…,n, то T делит НОК(T1,…,Tn). Если при этом отображение j биективно по всем переменным, то



T ³ НОК(T1,…,Tn)/НОД(T1,…,Tn).

 

Доказательство. Делимость НОК(T1,…,Tn) на T следует из утверждений 6.1 и 6.2. Без ущерба для общности докажем нижнюю оценку для п=2.

Пусть T1=t, T2=t, НОД(t,t)=d. Тогда t=p×d, t=q×d, НОК(t,t)=p×q×d, где (p,q)=1.

Предположим, что j(xi,1,xi,2)=j(xi+T,1,xi+T,2) для всех i, где T<p×q. Так как T/p×q×d, то при сделанном предположении T=p×x×d, где p/p, x/q, d/d, причём, равенства p=p и x=q не выполнены одновременно, иначе было бы T³p×q.

Пусть для определённости p<p. Тогда в последовательности Y® имеют место повторы через каждые q членов, где q=p×q×d (так как T/q). Следовательно, для всех натуральных i

j(xi,1,xi,2)=j(xi+q,1,xi+q,2).

 Так как t/q, то для всех i верно

xi+q,2=xi,2, и последнее равенство принимает вид:

 

j(xi,1,xi,2)=j(xi+q,1,xi,2).                                                 (6.1)

По условию (p,q)=1, значит и (p,q)=1. Поэтому t не делит q, то есть, xi,1¹xi+q,1 для некоторых i. Последнее неравенство несовместимо с (6.1) при биективности отображения j по первой переменной. Следовательно, T³p×q.                                        ¨

6.2. Граф отображения

Пусть имеется отображение j:X®Y, где X и Y - конечные множества мощности n и m соответственно, n,m>1. Отображению j поставим в соответствие  ориентированный двудольный граф G(j)=(XÈY,U), где XÈY - множество

вершин, U - множество дуг, и пара (x,y)ÎU Û xÎX, y=j(x)ÎY. Граф G(j) называют графом отображения j.

Из однозначности отображения j следует, то полустепень исхода любой вершины xÎX

равна 1 и êUê=êXê=n.

Полустепень захода py вершины y

графа G(j) равна числу прообразов элемента y относительно отображения j, 0£py£п. При этом
=п.



Если j - преобразование п-множества X, то графом преобразования j называют ориентированный граф G(j)=(X,U) с множеством вершин X и множеством дуг U, где (x,y)ÎU Û y=j(x).

Полустепень захода px равна 1 для всех xÎX тогда и только тогда, когда j биективно.

Граф G(j) преобразования j состоит из r компонент связности, 1£r<n, каждая из которых представляет собой простой цикл и, в случае небиективного преобразования, возможно, несколько подходов к этому циклу.

Структурными характеристиками графа G(j) являются число компонент связности, число циклических вершин, число циклов и число подходов к циклам заданной длины и др. Неподвижный элемент преобразования j образует петлю в графе G(j).

Граф G(j) биективного преобразования j (подстановки на множестве Х) состоит из r независимых циклов, 1£r£n. Если ki - число циклов длины i в графе G(j), iÎ{1,2,...,n}, то:

,

где 0£ki£n. Цикловая структура такого графа записывается в виде набора символов
, в котором опускаются все компоненты
, для которых ki=0.

Преобразования j и y множества X называются подобными, если найдётся биективное преобразование d того же множества, при котором j = d-1×y×d.

Отношение подобия на множестве преобразований есть отношение эквивалентности.

Теорема 6.3.

Преобразования j и y множества X

подобны тогда и только тогда, когда графы G(j) и G(y)

изоморфны.

Доказательство. Если преобразования j и y множества X

подобны, то у=j(х) тогда и только тогда, когда d(у)=y(d(х)). Следовательно, графы G(j)

и G(y) изоморфны, так как отличаются лишь переобозначением вершин с помощью подстановки d. Обратное утверждение доказывается рассуждениями в обратном порядке.                                                                                                                                    ¨

6.3. Характеристики периодичности преобразования

Преобразованию j конечного множества X и элементу xÎX поставим в соответствие последовательность F={ji}



i=0,1,2,… над полугруппой всех преобразований множества X и последовательность Fх над X:

Fх = {ji(х)} i=0,1,2,…

В силу конечности множества X обе последовательности содержат конечное число элементов, при этом если i–й и j–й члены любой из этих последовательностей совпадают, i<j, то совпадают их (i+r)–й и (j+r)–й члены, r=1,2,… Следовательно, обе эти последовательности являются периодическими.

Периодом (предпериодом)

элемента x относительно преобразования j называется период (предпериод) последовательности Fх. Обозначим их tx,j и пx,j

соответственно (или tx и пx, если преобразование j фиксировано).

Утверждение 6.3. 1) Если x – циклическая вершина графа G(j), то пx=0 и tx равен длине цикла, которому принадлежит вершина x.

2) Если x

– ациклическая вершина графа G(j), то пx равен длине подхода к циклу в графе G(j), начинающегося из вершины x, и tx

равен длине цикла той компоненты связности, которой принадлежит вершина x.

Доказательство. Из определения предпериода пx

следует, что повторы в последовательности Fх

имеют место лишь для членов с порядковым номером пx+1 и больше. Следовательно, первые пx членов не могут быть циклическими вершинами графа G(j).

Из определения периода tx следует, что периодический отрезок последовательности Fх образует цикл графа G(j).                                                             ¨

Периодом (предпериодом)

преобразования j называется период (предпериод) последовательности F, обозначим их tj и пj.

Утверждение 6.4. Пусть l1,l2, ... ,lr - все различные длины циклов графа G(j)

преобразования j. Тогда

tj

= НОК(l1,l2, ... ,lm).

Если j - обратимое преобразование, то пj=0, в противном случае пj

равен наибольшей из длин подходов к циклам графа G(j).

Доказательство. Из определения периода преобразования и утверждения 6.3 следует, что

tj=НОК(tx /xÎX)=НОК(l1,l2, ... ,lm);   пj=max{пx/xÎX}.                             ¨



Если j биективно, то первые tj членов последовательности F образуют циклическую группу <j> порядка tj.

Для периода преобразования j п-множества X и периода вектора xÎX относительно преобразования j верны оценки:

1£tx£п;       1£tj£п!.

Обе нижние оценки достигаются для тождественного преобразования. Первая верхняя оценка достижима при любом множестве X, вторая достигается лишь при множествах X мощности не более 2.

Пример 6.1.

Определим период и цикловую структуру преобразования j множества V3 регистра правого сдвига с одной обратной связью f(x1,x2,x3) = x1Åx2Åx3.

Из следствия 1 теоремы 5.4. имеем, что j – биективное преобразование. Построим независимые циклы графа G(j). При построении очередного цикла выбираем в качестве начальной вершины x ту, которая не фигурировала при предыдущих вычислениях, и вычисляем элементы последовательности Fх

до тех пор, пока впервые не выполнится равенство jl(x)=x, означающее, что элемент x

принадлежит циклу длины l.

В нашем примере вычисления дают следующие результаты:

1) j(0,0,0)=(0,0,0), значит t(0,0,0)=1;

2) j(0,0,1)=(1,0,0), j(1,0,0)=(1,1,0), j(1,1,0)=(0,1,1), j(0,1,1)=(0,0,1), значит t(0,0,1)= t(1,0,0)= t(1,1,0)= t(0,1,1)=4;

3) j(0,1,0)=(1,0,1), j(1,0,1)=(0,1,0), значит t(0,1,0)=t(1,0,1)=2;

4) j(1,1,1)=(1,1,1), значит t(1,1,1)=1.

Таким образом, цикловая структура преобразования j имеет вид (1[2],2[1],4[1]);

период tj преобразования j равен НОК(1,2,4)=4.

6.4. Полноцикловые преобразования

Особый интерес для криптографических приложений представляют преобразования с экстремальными периодическими свойствами.

Преобразование j п-множества называется полноцикловым (п.ц.), если граф G(j) представляет собой цикл длины п. Всякое п.ц. преобразование j биективно, и tx,j=tj=п для всех xÎX.

Теорема 6.4.

Число различных п.ц. преобразований n-множества равно (n-1)!.

Доказательство. Построение полного цикла из элементов n-множества X можно рассматривать как размещение на n



свободных позициях окружности всех n различных элементов множества X. Число различных таких размещений равно числу различных перестановок элементов n-множества, то есть, равно п!.

В то же время, перестановки элементов эквивалентны, если отличаются лишь параллельным сдвигом, так как представляют один и тот же цикл преобразования. Следовательно, множество всех построенных циклов разбивается на классы эквивалентных циклов, где в каждом классе содержится по п циклов. Таким образом, число п.ц. преобразований п-множества равно числу неэквивалентных циклов, то есть (п-1)!.                                                                                                                                        ¨

Пример 6.2. Линейный конгруэнтный генератор (ЛКГ).

Пусть Еk - кольцо вычетов по модулю k, j - преобразование ЛКГ множества Еk, если для любого хÎЕk:

j(x)=(a×x+b)modk,

где a, b и k – константы из Еk, называемые множителем, сдвигом, и модулем соответственно.

ЛКГ имеет период не более k. Для любых k и x имеются константы a и b, при которых tj=k. Такие генераторы называют ЛКГ полного (или максимального) периода. Приведём без доказательства следующую теорему [61].

Теорема 6.5.

Преобразование ЛКГ имеет период k Û:

1)          (b,k)=1;

2)          a-1 кратно любому простому делителю числа k;

3)          a-1 кратно 4, если k кратно 4.                                                                           

В частности, если k=2r, то tj=2r тогда и только тогда, когда

b - нечётное число и аº1(mod4).

Теорема 6.6.

Биективное преобразование j n-множества X является п.ц. тогда и только тогда, когда для любого отличного от константы отображения y:X®Y, где êYê³2, отображения y и y×j различны.

Доказательство. Пусть для п.ц. преобразования j множества X, для любого xÎX



и указанного отображения y:

y×j(х)=y(х).                                                         (6.2)

Тогда для любого натурального t и любого xÎX:

y×jt(х) =

y(х),

а это с учётом полноцикловости преобразования j означает, что отображение y - константа. Имеем противоречие, из которого вытекает, что отображения y и y×j различны.

Пусть теперь j - неполноцикловое биективное преобразование множества X, и X’ – подмножество множества X, образующее некоторый цикл графа G(j). Определим отличное от константы отображение y:X®Y, где Y={y1,y2,…}: y(х)=y1

для всех хÎX’ и y(х)=y2

для всех хÎX\X’. При таком y для любого xÎX выполняется равенство (6.2). Следовательно, отображения y и y×j совпадают.                                                              ¨

Пусть j и y - преобразования множеств Х(n) и Х(n-1) соответственно, где |Х|=k и y задано подсистемой системы j:

j = {f1(x1,x2,...,xn-1),...,fп-1(x1,x2,...,xn-1),fп(x1,x2,...,xn)},

y = {f1(x1,x2,...,xn-1),...,fп-1(x1,x2,...,xn-1)}.

Рассмотрим критерий полноцикловости преобразования j. Каждому пути s=(s1,s2,…,st)

в графе G(y) поставим в соответствие преобразование d(s):

  d(s)=
,                                                   (6.3)

где для вершины а=(а1,а2,…,ап-1)ÎХ(n-1) графа G(y) под fn(a,xn)

понимается подфункция fn(а1,а2,…,ап-1,xn), реализующая преобразование множества Х.

Теорема 6.7. Преобразование j является п.ц. тогда и только тогда, когда y - п.ц. преобразование множества Х(n-1) и d(s) – п.ц. преобразование множества Х, где s - цикл в G(y).

Доказательство. Покажем корректность формулировки теоремы, ведь при п.ц. преобразовании y в качестве преобразования d(s) множества Х может быть рассмотрено kn-1

различных преобразований в зависимости от начала отсчёта вершин цикла s. Для этого убедимся, что при п.ц. преобразовании y все эти преобразования подобны.



Действительно, если s=(s1,s2,…,st-1,st), s’=(s2,s3,…,st,s1), где t=kn-1, и d(s)

– п.ц. преобразование множества Х, то из этого следует, что d(s) - биективно и в силу (6.3) подфункция fn(a,xn) при любом аÎХ(n-1)

реализует также биективное преобразование. Следовательно, биективно и преобразование d(s’) как композиция биективных преобразований, где

d(s’) = fn(s2,xn)×fn(s3,xn)× …×fn(st,xn)×fn(s1,xn).

Отсюда и из (6.3) следует подобие преобразований d(s) и d(s’):  

d(s’) = fn(s1,xn)-1×fn(s1,xn)×d(s’) = fn(s1,xn)-1×d(s)×fn(s1,xn).

То есть, независимо от начала отсчёта вершин цикла s графа G(y) преобразование d(s)

является п.ц.

Пусть Fх[kn] - отрезок последовательности Fх, состоящий из её первых kn членов, хÎХ(n). Разобьём Fх[kn] на k последовательных отрезков Fх[kn]1, …, Fх[kn]k по kn-1

членов.

Если преобразования y и d(s) п.ц., то, судя по первым п-1 координатам, все члены отрезка Fх[kn]i различны в силу полноцикловости преобразования y, i=1,2,…k. В то же время, судя по п-й координате, последние члены отрезков Fх[kn]1, …,Fх[kn]k различны в силу полноцикловости преобразования d(s). Следовательно, все члены отрезка Fх[kn] различны, и j - п.ц. преобразование.

Если j - п.ц. преобразование множества Х(n), то y - п.ц. преобразование множества Х(n-1), так как в этом случае для периодов tj и ty выполняются соотношения:

ty£kn-1,       kn=tj £ ty×k.

Далее, если j и y - п.ц. преобразования множеств Х(n) и Х(n-1)

соответственно, то для периода td(s)

преобразования d(s) выполняются равенства:

kn = tj = ty×td(s) = kn-1×td(s).

Следовательно, d(s) – п.ц. преобразование множества Х.                                                  ¨

Следствие 1. Пусть ji - биективное треугольное преобразование множества Х(i), задаваемое системой координатных функций



ji

= {f1(x1), f2(x1,x2), ... , fi(x1,x2,...,xi)}, i=1,2,…                              (6.4)

Преобразование jп является п.ц. тогда и только тогда, когда для всех i=1,2,…,п

преобразования di(si-1) множества Х - п.ц., где при i>1

путь si-1=
- цикл в графе G(ji-1) и di(si-1) =
,   d1(s0)=j1=f1(x1).

Доказательство. Если преобразование jп

множества Х(n) является п.ц., то, применяя п-1 раз прямое утверждение теоремы 6.7 для i=n, n-1,…, 2, получаем, что преобразование ji-1 множества Х(i-1) и преобразование di(si-1) множества Х также являются п.ц. Следовательно, для i=1,2,…,п

преобразования di(si-1) множества Х являются п.ц.

Если для i=1,2,…,п преобразования di(si-1) множества Х являются п.ц., то, применяя п-1 раз обратное утверждение теоремы 6.7 для i=2, 3,…, n, получаем, что из полноцикловости преобразований ji-1

и di(si-1) следует полноцикловость преобразования ji множества Х(i).                                                                                                                    ¨                                                                                        

Следствие 2. Пусть в условиях теоремы 6.7 j и y - преобразования множеств Vn и Vn-1 соответственно. Преобразование j является п.ц. тогда и только тогда, когда y - п.ц. преобразование множества Vn-1 и

fп(x1,x2,...,xn)=g(x1,x2,...,xn-1)Åxn,

 где вес функции g(x1,x2,...,xn-1) нечётен.

Доказательство. В данных условиях d(s) есть преобразование множества {0,1}, поэтому если s - цикл в графе G(jп-1), то для любого хÎ{0,1}

d(s)(х) = х Å
 = х Å
.

Очевидно, преобразование d(s)

п.ц Û
 нечётен.                                                           ¨

Следствие 3. Пусть биективное треугольное преобразование jп

множества Vп задано системой функций (6.4), где  fi(x1,x2,...,xi)=gi(x1,x2,...,xi-1)Åxi,

i=1,2,…,п,  и  g1

=1.

Преобразование jп является п.ц. тогда и только тогда, когда вес каждой из функций g2,…,gп нечётен.



Доказательство

- индукция по п с использованием следствия 2.                          ¨

Известно, что число п.ц. регистров сдвига длины п равно
, однако удобные критерии полноцикловости для регистровых преобразований не известны. Приведём принцип «склеивания-расклеивания», позволяющий строить п.ц. двоичные регистры сдвига небольших длин.

Теорема 6.8. Пусть j и y - биективные двоичные регистры сдвига длины n с обратными связями f(x1,x2,...,xn)

и f(x1,x2,...,xn)Å
соответственно, где а2,…,апÎ{0,1}. Тогда граф G(j) отличается от графа G(y) тем, что либо один цикл графа G(j) распадается на два цикла графа G(y), либо два цикла графа G(j) объединяются в один цикл графа G(y).

Доказательство. Так как j и y биективны, то f(x1,x2,...,xn)=x1Åg(x2,...,xп). Отсюда следует, что

j(0,а2,…,ап)=(а2,…,ап,g(а2,…,ап)),

j(1,а2,…,ап)=(а2,…,ап,g(а2,…,ап)Å1),

y(0,а2,…,ап)=(а2,…,ап,g(а2,…,ап)Å1),

y(1,а2,…,ап)=(а2,…,ап,g(а2,…,ап)).

Таким образом, если вершины (0,а2,…,ап) и (1,а2,…,ап)

лежат на одном цикле графа G(j), то в графе G(y) они лежат на разных циклах. И наоборот, если вершины (0,а2,…,ап)

и (1,а2,…,ап) лежат на разных циклах графа G(j), то в графе G(y) они лежат на одном цикле. На остальных вершинах из Vn преобразования j и y совпадают.        ¨                                             

Для построения п.ц. регистрового преобразования из исходного биективного двоичного регистра сдвига путём «склеивания» циклов нужно находить пары соседних по 1-й координате вершин (0,а2,…,ап)

и (1,а2,…,ап), лежащих на разных циклах, и изменять функцию обратной связи посредством добавления конъюнкции
. Если граф исходного регистра состоит из r циклов, то для построения п.ц. регистра требуется выполнить r-1 таких шагов.

6.5. Линейные регистры сдвига

Линейное преобразование пространства Р(n)

над полем Р не является п.ц. при п>0. Это следует из того, что нулевой вектор является неподвижным элементом всякого линейного преобразования. Тем не менее, длина цикла в графе линейного преобразования пространства Р(n)



может быть «весьма большой» и достигать величины kn-1, где k – порядок поля Р. Такие линейные преобразования называют преобразованиями максимального периода.

Рассмотрим условия максимальности периода преобразования j пространства Р(n)

линейным регистром сдвига (ЛРС) с функцией обратной связи an-1×хn+...+a1×х2+a0×х1, где a0,a1,…,an-1ÎР. Матрица Аj

преобразования j имеет вид:

Аj =
.

Матрица Аj называется сопровождающей матрицей данного ЛРС. Для реализации преобразования регистра левого сдвига вектор (х1,х2,…,хп) умножается на матрицу Аj слева.

ЛРС длины п

максимального периода обозначим ЛРСmax-п. Особый интерес в криптологии к ЛРСmax-п объясняется удобством их реализации и доказуемостью их высоких периодов (при подходящих п) в отличие от многих нелинейных преобразований. Ведь непосредственное вычисление периода преобразования (см. пример 6.1) может быть выполнено лишь для множеств небольшой мощности.

Преобразование j ЛРС имеет максимальный период в том и только в том случае, если циклическая группа <j> имеет порядок kn-1, или иначе, матрица Аj имеет порядок kn-1 как элемент группы линейных преобразований множества Р(n). Выразим эти условия через характеристики обратной связи.

Функции обратной связи f(x1,x2,…,xn) ЛРС однозначно соответствует многочлен F(l) степени n над полем Р:

F(l)=ln- an-1×ln-1- an-2×ln-2-...- a1×l- a0,

называемый характеристическим многочленом этого ЛРС. Матрица Аj

является корнем многочлена F(l), и если F(l) неприводим над Р, её порядок совпадает с порядком многочлена F(l). Поэтому преобразование j имеет максимальный период тогда и только тогда, когда F(l) - примитивный многочлен, то есть:

1)  F(l) неприводим над полем Р;

2) F(l) делит многочлен 
  и не делит ни один из многочленов вида ld-1, где d/kn-1 и d¹kn-1.

Построение примитивных многочленов в общем случае связано со сложными вычислениями. На практике используются таблицы примитивных многочленов.



Для двоичных ЛРС из условий примитивности многочлена F(l) вытекает следующее утверждение.

Утверждение 6.5. Если многочлен F(l) степени n>1 неприводим над полем GF(2), и 2n-1 – простое число, то преобразование ЛРС множества Vn c характеристическим многочленом F(l) имеет максимальный период.

Доказательство. Из простоты числа 2n-1 следует, что имеется лишь один делитель d числа 2n-1, отличный от 2n-1, а именно, d=1. Осталось заметить, что F(l) не делит многочлен l-1 и делит многочлен 
, так как все элементы поля GF(2п), кроме единицы, имеют в мультипликативной группе этого поля порядок 2n-1. Следовательно, F(l) примитивен.                                                                                         ¨                                                                                                                                                       

Утверждение 6.6. Примитивный многочлен F(l) над полем GF(2) содержит нечётное число членов.

Доказательство. В противном случае единица поля GF(2) является его корнем. ¨                                                                                                                                                                

Утверждение 6.7. Если многочлен F(l) над полем GF(2) примитивен, то  примитивен и многочлен  ln×F(1/l).

Последнее утверждение позволяет сократить в два раза таблицы примитивных многочленов над полем GF(2).                                                                                                                                   

6.6. Аффинные преобразования максимального периода

      

Биективное аффинное преобразование y пространства Р(n) над полем Р порядка k, граф которого содержит цикл длины kn-1, назовём преобразованием

максимального периода. Определим условия максимальности периода аффинного преобразования.

Утверждение 6.8. Пусть j - линейное преобразование пространства Р(n)

и элемент х множества Р(n) имеет предпериод т и период t относительно преобразования j. Тогда вектор eх, определяемый выражением



 eх=jт(х)+jт+1(х)+…+jт+t-1(х),                                         (6.5)

есть неподвижный элемент преобразования j.

Доказательство. Так как преобразование j линейно, то

j(eх)=jт+1(х)+jт+2(х)+…+jт+t-1(х)+jт+t(х).

По утверждению 6.3 вершины ji(х) графа G(j) при i³т являются циклическими и лежат на цикле длины t, поэтому jт+t(х)=jт(х). Следовательно, j(eх)=eх.                      ¨                                   

Таким образом, каждому элементу хÎP(n)

соответствует неподвижный элемент линейного преобразования j, определяемый выражением (6.5), обозначим его eх,j.

Аффинные преобразования y1 и y2 пространства P(n) назовём а-параллельными, где а - ненулевой вектор пространства P(n), если y1(х)-y2(х)=а для всех хÎP(n). Заметим,  что а-параллельные преобразования y1 и y2 либо оба биективны, либо оба небиективны.

Теорема 6.9. Пусть j - биективное линейное преобразование пространства P(n) над полем Р характеристики p, и y есть а-параллельное ему аффинное преобразование. Тогда j и y оба либо являются, либо не являются преобразованиями максимального периода.

Доказательство. По условиям теоремы y(х)=j(х)+а для всех хÎP(n), где а¹и, и - нулевой вектор пространства P(n). Отсюда с использованием индукции по i несложно вывести равенство, верное для любого хÎP(n) и любого натурального i:

yi(х) = ji(х)+ji-1(а)+ji-2(а)+…+j(а)+а.                               (6.6)

По утверждению 6.3, последовательность {ji(а)}, i=1,2,…, является периодической с периодом tа,j, равным длине цикла, которому принадлежит вектор а. Тогда по утверждению 6.8 неподвижным элементом преобразования j является элемент eа,j=jl-1(а)+…+j(а)+а при l=tа,j.

По теореме 6.1 последовательность {ji(а)+…+j(а)+а}, i=0,1,2,…, является периодической с периодом t, где

t/d(eа,j)×tа,j                                                       (6.7)



и d(х) есть порядок элемента х как элемента аддитивной группы пространства Р(n). Очевидно, d(х)=1 при х=0 и d(х)=р в противном случае.

Из равенства (6.6) имеем, что последовательность {yi(х)} есть сумма периодических последовательностей {ji(х)} и {ji(а)+…+j(а)+а}, i=1,2,…, с периодами соответственно tх,j и t. Значит, по теореме 6.2 с учётом равенства (6.7) для периода tх,y последовательности {yi(х)} выполнено:

tх,y

/НОК(tх,j,d(eа,j)×tа,j).                                           (6.8)

       

Если j - преобразование максимального периода, то оно имеет единственный неподвижный элемент – вектор и, и его порядок равен 1. Поэтому  d(eа,j)=1 и из (6.8) при х=а имеем:

tа,y/tа,j

.                                                        (6.9)

С другой стороны, из равенства (6.6) следует, что ji(х)=yi(х)-yi(u) для всех хÎP(n) и любого натурального i. Значит, по теореме 6.2 tх,j/НОК(tх,y,tu,y). Учитывая, что векторы а и u принадлежат одному циклу преобразования y, из последнего соотношения получаем при х=а, что tа,j/tа,y.

Отсюда и из (6.9) заключаем: tа,y=tа,j= kn-1.

Пусть теперь биективное аффинное преобразование y пространства Р(n) есть преобразование периода kn-1. Вектор а не является неподвижной точкой преобразования y, так как его прообраз есть вектор и, поэтому tа,y=kn-1. Тогда из равенства (6.8) при х=а следует, что

(kn-1)/d(eа,j)×tа,j .

Так  как  величина  d(eа,j)  равна  либо  1,  либо  характеристике  р  поля  Р,  то  (kn-1,dа,j)=1, поэтому из последнего соотношения получаем, что (kn-1)/tа,j. То есть,  tа,j=kn-1, и j - преобразование максимального периода.                                                    ¨

6.7. Задачи и упражнения

6.1. Пусть {xi} и {yi} - периодические последовательности над кольцом вычетов по модулю k с периодами t1 и t2 соответственно, где НОД(t1,t2)=1.



1) Докажите, что период t последовательности {(xi+yi)modk} равен t1×t2. Каково наименьшее значение t, если условие НОД(t1,t2)=1 не выполнено? Чему оно равно?

2) При каких а и b период t последовательности {(а×xi+b×yi)modk} равен t1×t2?

6.2. Пусть {xi} - периодическая последовательность над множеством Х с периодом t.

1) Каков период последовательности {xr×i}, где r

– натуральное?

2) Каков период последовательности, полученной из {xi} изъятием подпоследовательности {xr×i}, где r

– натуральное?

3) Каковы периоды последовательностей из пунктов 1),2), если {xi} не содержит одинаковых членов?

6.3. Пусть j - преобразование регистра левого сдвига множества Vn с обратной связью f. Постройте граф преобразования j, определите предпериоды и периоды нулевого вектора и преобразования j, если:

а) n=4,  f(x1,x2,..., x4) = x1Åx2×x4;

б) n=4,  f(x1,x2,..., x4) = x1×x3 Åx2×x4Å1;

в) n=5,  f(x1,x2,..., x5) = x2×x3×x5Åx3×x4 Åx2×x4Åx2Åx1Å1;

г) n=5,  f(x1,x2,..., x5) = x2×x3×x4×x5Åx1×x3×x4 Åx2×x4Åx3Åx2Åx1Å1.

6.4. Какова цикловая структура и период аффинного преобразования j множества Vn, где j(x)=E×xÅa, E – единичная матрица,  а¹0.

6.5. Какова цикловая структура и период преобразования jk, если j - полноцикловое преобразование множества Vn?

6.6. Является ли полноцикловым преобразование j(х)=а×х+b кольца вычетов по модулю 2n, реализуемое линейным конгруэнтным генератором, если:

а)  n=10, a=10, b=7;

б)  n=10, a=9, b=6;

в)  n=10, a=9, b=9.

6.7. Является ли полноцикловым преобразование j множества Vn:

а) n=3, j={x1Å1, x1Åx2,  x1Úx2Åx3};

б) n=3, j={x1, x1Åx2Å1,  x1Úx2Úx3};

в) n=4, j={x1, x1Åx2,  x1×x2Åx3, x1×x2Åx2×x3Åx4}.



6.8. Пусть f(x1,x2,…,xn) – функция обратной связи двоичного ЛРСmax-п. Докажите, что регистр сдвига с обратной связью f(x1,x2,…,xn)Å
×…×
 является полноцикловым.

6.9. Пусть f(x1,x2,…,xn)=an×хnÅ...Åa2×х2Åх1

– функция обратной связи биективного преобразования двоичного (левого) ЛРС. Докажите, что преобразование регистра сдвига с обратной связью f(x1,x2,…,xn)Å
×…×
 не имеет неподвижных элементов тогда и только тогда, когда anÅ...Åa2=1.

6.10. Пусть j - преобразование двоичного ЛРСmax-п, y=хÅа - аффинное преобразование множества Vn. Определите неподвижные элементы преобразования y×j×y.

6.11. Пусть j - преобразование множества Vn, y - инволюция на множестве Vn. Докажите, что tj=ty×j×y.

6.12. Каков период аффинного преобразования множества Vn y=jÅa, где j - линейная инволюция и a – ненулевой вектор?

6.13. Пусть j - преобразование двоичного ЛРСmax-п. Каков период преобразования y=jr, где r – целое; степень числа 2?

6.14. Докажите, что многочлен над полем GF(2), не содержащий нечётных степеней переменной, не является примитивным.

6.15. Является ли примитивным многочлен f(l) над полем GF(2):

а)  f(l) = l5Ål2Ål;

б)  f(l) = l5Ål2ÅlÅ1;

в)  f(l) = l6Ål4Å1;

г)  f(l) = l11Ål10Ål9Ål7Ål6Ål5Ål2ÅlÅ1.