Дискретная математика и криптология
Глава 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. Цикловая структура такого графа записывается в виде набора символов
Преобразования 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)=
где для вершины а=(а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=
Доказательство. Если преобразование 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)Å
Доказательство. Так как 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,…,ап), лежащих на разных циклах, и изменять функцию обратной связи посредством добавления конъюнкции
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) делит многочлен
Построение примитивных многочленов в общем случае связано со сложными вычислениями. На практике используются таблицы примитивных многочленов.
Для двоичных ЛРС из условий примитивности многочлена 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 и делит многочлен
Утверждение 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)Å
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.
