Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

361

Напомним, что унитарным многочленом называется многочлен со старшим коэффициентом равным единице. Зафиксируем унитарный многочлен Р(х)=хт - Рт_1Хт'' Г|Х - Г0 еИ[х] степени т>0 и обозначим через Ьк(Р) се- -

мейство всех ЛРП над К. с характеристическим многочленом-Р(х). Тогда непос­ редственно из определения 2 вытекает

Утверждение 1. Любая ЛРП иеЬк(Р) однозначно задается своим нача­

льным вектором и(0,...,т-1). Если |К| < оо, то | Ьк(Р)| = |Р|т.

При исследовании свойств ЛРП весьма плодотворным оказывается ал­ гебраический подход, связанный с введением на К” различных операций.

Определение 3. Суммой последовательностей и,у е К." и произведени­

еми на константу ге К. называют, соответственно, последовательности \у = и + V и 2 = г • и, определяемые соотношениями

\у(1) = и(1) + у(1), 2(1) = Г • и(1) , 1€

Очевидно, что группоид (К00, +) есть абелева группа с нулем (0) и для любых а, Ь € К., и, у € К00 справедливы соотношения

(аЬ) • и = а • (Ь • и),	(а+Ъ) • и = а • и + Ь • и,
а(и+у)=аи+ау, еи=и.	(3)
В частности, если Р - поле, то определенные выше операции задают на

Р00 структуру левого векторного пространства РР°°, имеющего, очевидно, беско­

нечную размерность. Из определений 2, 3 легко следует Утверждение 2. Для любого унитарного многочлена Р(х)еК.[х] подм­

ножество Ьк(Р)сК00есть подгруппа группы (К00,-!-), выдерживающая умноже­ ние на элементы из К. Если Р - поле и Р(х)еР[х], то Ьк(Р) - подпространство пространства Р00.

Таким образом, в случае, когда Р - поле, можно говорить о базисе про­ странства Ьк(Р)- Мы, однако, не будем рассматривать эту простейшую ситуа­ цию отдельно, а введем и изучим аналог понятия базиса пространства для про­ извольного семейства Ьр(Р).

Определение 4. Для унитарного многочлена Р(х)еК.[х] степени т>0 систему последовательностей и1,...,итеЬк(Р) назовем базисом семейства Ья(Р),

если для любой последовательности и€Ьк(Р) существует единственный набор констант сь...,стеК.такой, что

и=С|и1+...+стит.

Доказательство существования и описание базисов семейства Ьк(Р)

дает

Утверждение 3. В обозначениях определения 4 система последовате­ льностей 11|,...,итеЬя(Р) есть базис ЬК(Р) тогда и только тогда, когда состав­

ленная из начальных векторов этих последовательностей матрица

362

с/ =

ит( 0 , т - 1 )

обратима над кольцом К.

ДОКАЗАТЕЛЬСТВО. Если И - обратимая матрица, то для любой по­ следовательности иеЬк(Р) единственный набор (с^Сг,.-. .,ст)еК т такой, что

и(0,1,... ,т - 1)=(с],с2,... ,ст) 11.

Рассмотрим последовательность у=С1и|+...+стит. По утверждению 2

уеЬк(Р). Кроме того, очевидно, что у(0,...,т - 1)=(с|,с2,...,ст)-11=и(0,1,...,т -1 ). Поэтому в силу утверждения 1 у=и, то есть сраведливо равенство и=С1и1+...+стцт.

Единственность представления последовательности и в этом виде сле­ дует из того, что это равенство влечет: и(0,1,... ,т - 1)=(с ],с2,... ,ст)-И Таким об­ разом, иь... .,ит - базис Е&(Р).

Наоборот, пусть и|,...,ит - базис Ь&(Р). Определим для каждого ке{1,...,т} ЛРП е^еЬ^Р) начальным вектором: е|<Р(0,...,гп,-1) - к-ой строкой

единичной матрицы Е размера т х т . По предположению каждая из последова­ тельностей екР представляется в виде

®к 111]+...^С^итНо тогда для матрицы С=(сц) размера шхш справедливы равенства

С-И=

= Е .

е т (0>—Ш -1)

Следовательно, У - обратимая матрица.

Следствие. Для унитарного многочлена Р(х) над полем Р размерность пространства Ьр(Р) равна степени многочлена Р(х).

Определим на К00 внешнюю операцию умножения слева на многочлены из К[х]. Для любых кеГ^ и иеК." положим

хк-и=у,

где у(1)=и(1+к), для 1€ Р^.

Другими словами умножение на хк есть сдвиг последовательности и на к шагов влево, и л и вычеркивание из и первых к членов

хк (и(0), и(1),...)=(и(к), и(к+1),...).

363

Определение 5. Произведением многочлена А(х) —^ акх к

к= О

напоследовательность и€К.°° называется последовательность А(х)иеК°° вида

т

Л(х)и = У] а к(х к • и ) . к=О

т
То есть А(х)и=\у, где и>(/) = У'/ак • м(г + А:) для	.
*=о

Теорема 1. Для любых А(х),В(х)еК.[х] и и,уеК°° справедливы равенства

1.А(х)-(и+у)=А(х)-и+А(х)-у

2.(А(х)+В(х))и=А(х)-и+В(х)-и

3.(А(х)-В(х))-и=А(х) (В(х)-и)

Первые два равенства легко выводятся из определения 5. Для доказа­ тельства последнего равенства заметим, что для любых а,ЪеК и к^е N2 из вве­

денных определений легко следует равенство ахк-(Ьх'-и)=аЪхк+'-и. Поэтому, если

А (х) = ]^ а кх к , В(х) =	,
к>0	з>0

то из первых двух равенств, указаных в теореме, следуют равенства

(	\
(А(х)В(х))и=	и = ^ а кх к(Ь]х-'-и) =
к,]>0	ко>0

= 2 а кх к(в (х)-и) = А (х )-(В (х )и )).

к>0 Следствие. Любая ЛРП и над кольцом К имеет бесконечно много хара­

ктеристических многочленов.

Определение 7. Характеристический многочлен ЛРП и, имеющий наи­

меньшую возможную степень, называется ее минимальным многочленом, а его степень называется рангом ЛРП и и обозначается через гап§ и.

Очевидно, что ранг ЛРП определяется однозначно. В то же время, ми­ нимальных многочленов у одной ЛРП может быть несколько, и даже бесконеч­ но много.

Определение 8. Аннулятором последовательности и€К°° называется

множество

1

364

Апп(и)={Н(х)еК[х]: Н(х)и=(0)}.

Очевидно, что Апп(и) - идеал кольца К[х], последовательность иеК00 есть ЛРП над К тогда и только тогда, когда в этом идеале есть унитарные мно­ гочлены, и минимальный многочлен ЛРП и есть любой унитарный многочлен наименьшей степени из Апп(и).

Теорема 2. Любая ЛРП и над полем Р имеет единственный минималь­

ный многочлен 0(х)еР[х] и он удовлетворяет равенству Апп(и)=Р[х]0(х).

ДОКАЗАТЕЛЬСТВО. Так как Р[х] - кольцо главных идеалов, то суще­ ствует единственный унитарный многочлен 0[х] еР[х] такой, что Апп(и)=Р[х]0(х). Откуда следует, что О(х) - характеристический многочлен ЛРП и, на который делится любой другой ее характеристический многочлен. Следовательно, О(х) - единственный минимальный многочлен ЛРП и.

В дальнейшем минимальный многочлен ЛРП и над полем будем обо­ значать через т и(х).

Теорема 3. Для любого унитарного многочлена 0(х)еК.[х] и любой по­

следовательности иеК.00 следующие утверждения эквивалентны

(а) и - ЛРП с единственным минимальным многочленом О(х);

(б) Апп(и)=К[х]-0(х).

ДОКАЗАТЕЛЬСТВО. Покажем, что из (а) следует (б). Так как О(х)и=(0), то К[х]- 0(х)еАпп(и). Наоборот, пусть Н(х)еАпп(и). Разделим Н(х) с остатком на О(х):

Н(х)=0(х)-О(х)+А(х), <!е§А(х)<<1едО(х).

Тогда А(х)еАпп(и), так как Н(х)и=О(х)и=(0). Следовательно, 0|(х)=0(х)+А(х) - унитарный многочлен из Апп(и) той же степени, что и 0(х), то есть О^х) - минимальный многочлен ЛРП и. Но тогда ввиду условия (а) 01(х)= О(х), то есть А(х)=0 и Н(х)е К[х] 0[х]. Импликация (б)=>(а) доказыва­ ется так же, как и в теореме 2.

Определение 9. Для элемента аеКАО и любого кеР^ последователь­

ность а[к] еК* элементов вида
аМ(1) =	а , 1еИо

называется биномиальной последовательностью порядка к+1 с корнем а. Теорема 4. Пусть многочлен Р ( х ) е Р [ х ] раскладывается над полем Р на

линейные множители и имеет каноническое разложение вида

Р(х) =(х - ах)к'+х -К

а5 *0,к5 >0,дпязе\,г.

Тогда базисом пространства Ьр(Р) является система биномиальных по­ следовательностей

а»\а?,Ка™,

Эта теорема позволяет находить произвольный 11(1) ЛРП и над полем,

заданной своим характеристическим многочленом Р(х) и начальным вектором

и(0,

Пример. и(1+4)=2и(1+3)+2и(1+2)+2и(1) над ОР(5). Начальный вектор и(0,...,3)=(0,3,0,2). Найти и(999). .

1) Раскладываем Р(х) на линейные множители (переходим, если нужно к полю разложения).

Г(х)=(х-2)3(х-1).

2) По теореме 4 ЛРП и представляется в виде линейной комбина­ ции 3-х биномиальных последовательностей с корнем 2 и одной с корнем 1.

	и = с02[0] + с, 2[|] + с22[2] + с31[0] ИЛИ
			/■ ■л
	11(1) = с 02' + с, */ *2'		1	>1 - 2	+ с 3Т
			1+ с
	3)	Используя известный начальный вектор и(0,...,3) составляем
	систему линейных уравнений. Полагаем 1=0,1,2,3.
	1 = 0	с0 + с 3	0		с0 —3
	1=1	2с0 + с, + с3 = 3		О	с, = 0
	1 = 2	4с0 + 4с, + с2 + съ = 0			с2 = 1
	1= 3	8с0 + 12с, + 6с2 + сг = 2			с3 = 2

4)Записываем ответ:

м(0 = 3-2' +

21-2 + 2, 1 > 0.

ч2у

Теперь вычислим и(999). Имеем ач'1=е, аеОР(ц), у нас а4=1, 24=1. Получим

1/(999) = 3 -2 999 + ^ 2 - + 2 = 3 .2 > + ^ 5 . 2 ' + 2 = 4 .

1

366

Напомним следующее понятие.

Определение 10. Последовательность иеО°° над множеством О. называ­

ется периодической, если существуют числа ХеГ^, *€1Ч, такие что для любого 1 > X

и0 +1)=и(1).

(*)

Длиной подхода Л(и) называется наименьшее ХеГ^, для которого су­ ществует 1е1Ч, такое что выполняется (*).

Периодом Т(и) называется наименьшее 1е]\, такое, что существует

Х е^ , для которого выполняется (*).

Все X и I, удовлетворяющие (*), описываются'следующим утверждени­

ем.

Утверждение 4. Числа X е IV] и 1е1Ч, удовлетворяют (*) тогда и только

тогда, когда Х>Л(и), Т(и)| I.

Утверждение 5. Всякая периодическая последовательность над полем

Р является ЛРП. Если Р - конечно, то верно и обратное.

Определение 11. Периодическая последовательность и называется чис­

то периодической или реверсивной, если А(и)=0, и вырождающейся, если для любого 1>Л(и): и(1)=0.

Утверждение 6. Любая периодическая последовательность и над полем

Р однозначно представляется в виде и=и0+иь где и<>- вырождающаяся, и! - чис­ то периодическая, при этом А(и)=Л(и0), Т(и)=Т(и|).

Определение 12. Многочлен Г(х) над Р называется периодическим, если

существует ХеР^,	:	Г(х) | х\х*-е)		(**).
Длиной подхода Л(1) называется наименьшее Хе1\|, для которого 3 1еМ,
такое что выполняется (*).			•	-

Периодом Т(1) называется наименьшее 1е]Ч, такое что существует Х е^ , для которого выполняется (*).

Утверждение 7. Пусть и - ЛРП над полем Р с минимальным многочле­ ном т и(х), тогда и - периодична тогда и только тогда, когда многочлен ши(х) - периодичен. При этом Т(и)=Т(ши(х)), А(и)= А (ти(х)).

Утверждение 8. Пусть Г(х) - унитарный многочлен над полем Р=ОР(ц),

характеристики р, с каноническим разложением

Г(х) = х1'81(х)к' ,К -8$(х)к>, Ь>0, к; >1,

Тогда

А(1)=1,

Т(0=[Т(§,),..,Т(&)]-РС,

V

367

где с=сот1еГ^, определяемая соотношением рс1 <к=тах{к!,...,к8}<рс.

То есть нахождение периода многочлена над конечным полем сводится к на­ хождению неприводимого многочлена неравного многочлену х.

'.Определение 13. Многочлен Т(х) над полем Р называется регулярным,

если Т(0)*0.

Утверждение 9. Пусть Г(х) - неприводимый, регулярный степени ш над Р=ОР(я), тогда Т(1) равен порядку его произвольного корня авполе разложе­ ния Р’=ОР(яш). При этом выполняется соотношение : Т(1)|яш-1 ; для любого г=1,...ш-1 : Т(1) не делит я-1.

Пример, найти период Р(х)=х4+х+е над ОР(2).

1)я"1-1=24-1=15=5-3

1€ {1,3,5,15}, 1 и 3 - не подходят, так как 3|яг-1 при г=2. {5,15}.

2)Проверим х5=е (то<1 Т(х)):

х5= х4-х (то<1 Т(х))=(х+е)-х= х2+х - несравнимо с е (т0<1 Т(х)). Значит период многочлена Т(х) равен 15.

Определение 14. Регулярный многочлен Т(х) степени т > 1 над полем

Р=ОР(я) называется многочленом максимального периода или примитивным многочленом, если Т(1)= я"1- 1. ЛРП и над полем Р=ОР(я), имеющая ранг ш > 1 и период ят-1 называется ЛРП максимального периода над Р.

Утверждение 10. Пусть и - ЛРП над полем Р=ОР(я) с регулярным ми­

нимальным многочленом ши(х)=Т(х) степени ш и пусть я',1>2, тогда эквивалент­ ны следующие утверждения:

(а) и - ЛРПМП;

(б) любая ЛРП уеЬР(1)\{0} является сдвигом ЛРП и, то есть у=хки для некоторого кеМ0;

(в) Р(х) - неприводим над Р и его корень а (в поле разложения Р’=ОР(Ят) многочлена Р(х) над Р) является примитивным элементом Р’;

(г) Р(х) - многочлен максимального периода над Р.

Следствие. Если Г(х) - многочлен максимального периода над Р=ОР(я),

то любая ненулевая ЛРП иеЬР(1) является.ЛРПМП.
Зафиксируем ао,...,аг.1еР и обозначим Ии(№) = Ыи(а0,К	число
«(0 = а0
и( 1 +1) = а х
решении системы уравнении:

К

и(/ + г -1 ) = ак_х

368

Величина Ыи(а) называется числом появлений вектора а на цикле

ЛРП и.

Утверждение 11. Пусть и - ЛРПМП ранга ш над Р=ОР(ц) и пусть г<т,

тогда

для любых ао,... ,аг! е Р:

Кц(а) = IЧ™ *’если(а0>• • •аг-1) * (°>•• • >°) [яш_г -1, иначе.

Следствие. Если и - ЛРПМП ранга ш над СР(ц), тогда каждый ненуле­ вой элемент поля встречается на цикле ЛРП и я"1'1раз, а нулевой элемент цш''-1 раз.

Подробное изложение данного материала с доказательствами всех ут­ верждений содержится в ПРИЛОЖЕНИИ 2.

Параграф 6.9 Вопросы гарантирования периодов выходных после­

довательностей автоматов при заданной входной последо­ вательности

Основным результатом по оценке снизу периодов выходных последо­ вательностей конечных автоматов, отвечающих их начальным состояниям и входным периодическим последовательностям является результат, представ­ ленный в теореме 2.2. работы: Трахтенброт Б.А., Барздинь Я.М. Конечные ав­ томаты (поведение и синтез). «Наука», М., 1970 г., й состоящий в том, что ми­ нимальный период V/ выходной последовательности автомата не превосходит величины ксо, где к - число состояний автомата, а со - минимальный период входной последовательности. В работах: Беркс А.В., Райт Д.Б. Теория логиче­ ских сетей. «Кибернетический сборник» вып:4, ИЛ, 1962; Кобринский Н.Е., Трахтенброт Б.А., Введение в теорию конечных автоматов. М., 1962 г., приве­ дены утверждения, суть которых состоит в том, что >У является делителем числа к'со при некотором к' <к.

В связи с большой сложностью проблемы нижней оценки периодов вы­ ходных последовательностей конечных автоматов при заданных начальном состоянии и входной периодической последовательности естественным подхо­ дом к ее удовлетворительному решению является выделение тех или иных классов автоматов в качестве объектов исследований. Например, ряд работ по­

369

священ вопросам периодичности выходных последовательностей линейных автономных автоматов, в частности, здесь выделяются работы, в которых ука­ зываются способы построения линейных рекуррентных последовательностей максимального периода в разнообразных алгебраических структурах.

В настоящем параграфе используется другой подход к решению по­ ставленной проблемы, заключающейся в предварительном решении промежу­ точной задачи - оценки снизу периода последовательности состояний автома­ та, отвечающей его начальному состоянию и входной периодической последо­ вательности. Эта задача решается в более общей постановке, а именно, речь идет об оценке характеристик почти периодичности последовательностей со­ стояний конечных автоматов.

Для периодической последовательности 3 периода со элементов конеч­ ного алфавита I вводится понятие меры ц(3, <1) приближенного периода ё. Ка­ чественно, ц(3,ё) трактуется как минимальная часть знаков последовательно­ сти 3, которые необходимо изменить для получения из 3 последовательности периода ё.

Основным результатом является теорема 1, дающая нижние оценки мер приближенных периодов последовательности состояний автомата, отвечающей его начальному состоянию и входной периодической последовательности.

Следствие 1 дает нижние оценки периодов этих последовательностей. В след­ ствии 2 указываются нижние оценки мер приближенных периодов выходной последовательности регистра сдвига, отвечающей его начальному состоянию и входной периодической последовательности.

Обозначения, основные понятия, вспомогательные результаты.

I, 8, О - произвольные непустые конечные множества с мощностями

т, |0|>2;

А=(1,8,0, (5,);е1, (Р);е1 ) - автомат с входным алфавитом I, мно­

жеством состояний 8, выходным алфавитом О, частичными функциями пере­ ходов (х,)ш и выходов (р),е1;

N - множество натуральных чисел Ыио=М0;

-I* - множество всех слов в алфавите I;

-1д “ множество всех смешанно-периодических последовательностей

в алфавите I. Напомним, что последовательность 3 из называется чисто­

периодической, если длина Ь ее предпериода равна нулю. Под периодом после­ довательности у здесь и далее будет пониматься ее минимальный период.

- 1^\у - множество всех последовательностей из / “ периода

370

-Ам(з,3) = 81,82,...,^,... - последовательность состояний автомата А;

-А(з,3) =у| ,уг,... ,у},... - выходная последовательность автомата А;

-ДЛЯ 3=11,12,...,^,... и з е 8

^ = б 1Н - 5!,5’ У] =Р1з5] . 5'=8;

I

-р(3,3') - расстояние Хемминга между словами 3, 3' одинаковой дли­

ны из I*;

-рк(3,3') - расстояние Хемминга между начальными словами длины к

последовательностей 3, 3' из /" ;

-(со,со') - наибольший общий делитель чисел со, со';

-[со,со'] - наименьшее общее кратное чисел со, со';

-со - Б делит со;

-191| - мощность множества 9?.

Для 3 =11,	из 1„ положим:
^У-Ч^-ц,... ,	—-^5, ->^]к	..,1]+к-1 ,

ССЮ(3)={1е1:Э]€Ы,1Г 1}.

Последнюю величину мы называем «содержанием» последовательно­ сти 3. Если понимать под последовательностью 3 элементов алфавита I ото­ бражение 3: N->1, то содержание 3 равно образу множества N.

Пусть 3, 3' - произвольные последовательности из /* с длинами под­

ходов Ь, Ь' и периодами со, со', соответственно. Легко доказывается следующее утверждение.

УТВЕРЖДЕНИЕ 1. При к->оо предел

Цт-^-рк ( 3 , 3 ')

к

существует и равен величине

ц(3,3')=-—-—тр[ю,(о](Зтах(1'’1' )+|),3 'тах(1-1-'>+’)

[со, ш ]

Данное утверждение является частным случаем следствия 1 работы: Бабаш А.В. Приближенные модели перестановочных автоматов. Дискретная математика. Т.9, вып. 1, 1997 г.

Определение 1. Приближенным периодом последовательности 3 е/* называется любое число \У из N. Величина р(3,\У)=тГр(3,3'), где нижняя грань берется по всем последовательностям 3' € 1^ ^ , называется мерой при­

ближенного периода \У (мерой приближения приближенного периода \У) по­ следовательности 3.