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

1 г

481

Следовательно, Р(х) удовлетворяет условию (2) теоремы 8 и последова­ тельность и однозначно представляется в виде

и = а 10а [,01 + а па{,] + а 12а |2] + а20а [20] + а 2|а^1] + а 30а '0].

Выражение (3) для 1-го члена этой последовательности имеет в рассма­

триваемом случае вид

и(0 = а 10е' + а, , 1	-е1+ а |2	е	+ а20(2е) + а211(2е) + а30(Зе) —
а 10 + а П !	+ а 12	с + (а20 + а211)•(2с) + &30(Зс) ,
а система линейных уравнений
и(0, т	-1 ) = 2	=1	х **а 8](°*т _ 1 )

для определения коэффициентов в этом представлении выглядит следующим образом:

	о
V	ОО)

е1 е1

(0е)°(2е)°	0 • (2е)°	(Зе)0>	гх 10	г° 1
0е’(2е)‘	1 • (2е)‘	(Зе)1
			Х11	е

е2	2е2	1 е2(2е)2	2-(2е)2	(Зе)2	Х ,2	е
е3	Зе3	3 -е3(2е)3	3 • (2е)3	(Зе)3	х20	0
е4	4е4	6 е 4(2е)4	4 • (2е)4	(Зе)4	Х21	Зе
и	5е5 1 0 е 5(2е)5		5-(2е)5	(Зе)5 ,	чхзо>

После преобразований в арифметике поля 2 5 эта система принимает вид

О	0	е	0	е	V 10Л	^0 ^
е	0 2е		2е	Зе	Х П	е
2е	е 4е		Зе	4е	х ]2	е
Зе	Зе Зе		4е	2е	Х 20	0
4е	е	е	4е	е	Х21	Зе
О	0	2е	0	Зе,	Чх 30>

Решая ее, получаем: (а1оап а 12а 2оа21аз0) =(е> е, е, 2е, 2е, 2е), т. е. для

всех 1 е N справедливо равенство

163ак.5

482

и(0 = 1+ 1+	е + (2 + 21)(2е)' + 2(3е)'
Отсюда, при 1 = 1986 находим	ч2 /У

и(1986)= 2 е + 4 • (2е)4ЛШ2 +2-(Зе)4АШ2=2е+4 -(2е)2 +2(3е)2 = 2 е + е + 3 е = е

Замечание 3. Теорема 8 может быть использована для описания общего члена ЛРП иеЬР(Р) и в случае, когда многочлен Р(х) не раскладывается над полем Р на линейные множители. В этой ситуации рассматривается поле раз­ ложения () многочлена Р(х) над полем Р и каноническое разложение (2) Р (х) над 0. Так как и€Ьд(Р), то можно утверждать, что общий член и(1) последова­ тельности и имеет вид (3) где а5к некоторые коэффициенты из расширения С! поля Р. Следует заметить, однако, что при сделанных предположениях в виде (3) представляется общий член любой ЛРП иеЬд(Р). Поэтому дополни­ тельное условие и е Ь<з(Р)пР“ накладывает некоторые ограничения на набор коэффициентов а* е' р. Смысл этих ограничений в случае, когда Р - конечное

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

П р и м е р 9. Вычислим над полем Р = 2г значение определителя

2	2	0	0		0
О 1	2	2	0		0
0	1	2	2 ...		0
й =
0		0	1	2	2
0		0	0	1	2 12x12

Как отмечено в примере 5, ё -есть член Д(11) ЛРП Д над Р с характери­ стическим многочленом Р(х) = х 2 - 2 х + 2 и начальным вектором Д (0,1 )=(2,

2).

Многочлен Р(х) не имеет корней в Р и потому ввиду условия </ецР(х)=2, он неприводим над Р, а его минимальное поле разложения () есть О = ОР(32).

В поле 0 многочлен Р(х) имеет 2 разных корня: а 0 и а ,, удовлетворя­ ющих соотношению ао +он =2.

По следствию теоремы 8 общий член ЛРП Д имеет вид ДО) = с0а'0 + с , а | , где коэффициенты с0 и с, системы линейных уравнений -

483

соа о + с , а “ = А(0) с0сс‘ +с,сс; =А(1).

Подставляя сюда значения начального вектора, получаем

	Гс0 + С[ = 2
	1с0а 0 + с,а,	= 2
	Пользуясь условием а 0 + а, = 2,	находим с0 = с, =	1 и
Д(1) = а{, + а } .
	В частности, й = Д (11) = а},1+ а}1 . Так кака8еОР(32), то а® = а 8,для
8 е	0,1. Поэтому а" = а„+2 + а®+2 =	+ а 2. Так как а 2 = 2 а 8 - 2 , то
а 8	= 2 а 2 - 2 а 8 = а 8 - 1 - 2 а 8 = 2 а 8 - 1	для 8 е 0,1.
Окончательно получаем:
	(1 = (2а0 - 1 ) + ( 2 а , - 1 ) = 2(а0 + а , ) -		2 = 2 .

Представление ЛРП над конечным полем с помощью функции "след”.

Пусть Р = ОР(я) - конечное поле характеристики р и (3 = ОР(ят) - его расширение степени т .

Определение 11. Следом из поля <3 в поле Р называется отображение й^ : (3 —» Р, ставящее в соответствие произвольному элементу а е (3 элемент

й ^ (а) = а + а ч +... + а чШ' .

О	аш
Функция йр (х)	иногда обозначается также через 1г^ (х) (если

достаточно акцентировать внимание лишь на мощностях рассматриваемых по­ лей) или просто — через й (х) (если из контекста ясно, какие поля имеются в виду).

Отметим сразу, что отображение йр* определено корректно, т. е. длялюбого

1 6 *

/

484

а е р выполняется включение й^ (а) € Р, поскольку очевидно, что й^ (а)4 = й^ (а). Основные свойства функции "след" перечисляет

Теорема 9. (а) Функция й^ есть линейное отображение пространства

Р Рна пространство РР .

(б) Если дана башня полей С! = ОР(ят) з ОР(як) => Р, то для любого а Р справедливо равенство

(в) Если минимальный многочлен элемента а е Р над полем Р имеет вид ца р (х) = х к - с к_,хк 1- ... - с0 , то к | т и

ДОКАЗАТЕЛЬСТВО, (а) Для любых а ,Ь еР и а,р е <2 из известного равенства (аа + рЪ)4 = а ча + рчЬ и определения 11 следует равенство й^ (аа + РЬ) = й (а ) -а + й(Р) • Ь. Следовательно, й^ - линейное отобра-

жение Р р в Рр . Так как Ат РР =1, то либо й (Р) = Р, либо й (Р) = 0. Послед-' нее равенство невозможно, так как оно означает, что все я"1элементов поля Р

являются корнями многочлена х + хч + ... + х ч степени я”*-1. Следовательно,

й(Р) = Р, т. е. й - отображение Р на Р.

(б)Из условия теоремы й свойств конечных полей следует, что к | т .

Пусть ш = к-п. Заметим, что справедливо равенство {0, 1,..., т-1} = {к$+1:

8 е 0, п —1,1 е 0, к —1}. Теперь утверждение (б) доказывается следующим об­

разом:

а

(в) Рассмотрим расширение Р(а) поля Р в р. Так как [Р(а) : Р] =

485

=(1е8,цв>р(х) =. к, то Р(ц) = =ОР(як) и к|ш, т.е. ш = кп для подходящего п е N.

Поскольку при сделанных предположениях а 4 = а, то справедливы равенства

а т	к	а И п - 1 )	= а + а +... + а = п • а .
(а)	= а + а 4	+... + а 4

Из свойств неприводимых многочленов над конечным полем следует равенство

Ц«.р00 = х к - с к_,хк-' - ^ ...-с0 = ( х - . а ) ( х - а я)•...• ( х - а 4"'),

которое дает соотношение

(а)= а + а 4 +... + а 4' ' = ск-1.

Отсюда, пользуясь утверждениями (б) и (а), получаем

1гчч”(а ) =

(^Г (а)) = 1гччк (па) = п • ^ (а) = п • ск_, = ^ ск-1 •

Основной результат, позволяющий описывать любую ЛРП над конеч­ ным полем с помощью функции "след", состоит в следующем.

Теорема 10. Пусть Р = ОР(я), О(х) - неприводимый многочлен степени т над Р, 0=<ЗР(ят) - минимальное поле разложения О(х) над Р и а - корень С(х) в р. Тогда для любой ЛРП и е ЬР(0(х)к+|), к е И, существует единствен­ ный набор констант ао,..., ак е О такой, что

ГП

Га	Л. Га г ч 1 ^ _1_ Л.	Га	^
	(а,а‘) + ...+

А

Любая последовательность и е Р30 вида (4) принадлежит ЬР(0(х)к+1).

ДОКАЗАТЕЛЬСТВО. При доказательстве данной теоремы мы исполь­ зуем следующее известное из теории конечных полей вспомогательное утве­ рждение.

Пусть/(х) —неприводимый многочлен степени п над полем Р=ОР(ф, д~р', и А=Р(а) -расширение поля Р, порожденное корнем а многочлена/(х). Тогда справедливы следующие утверждения:

а) Р - минимальное полеразложения многочлена/(х) над Р, причем/(х) имеет в Рровно празличных корней

	486
а, сР,	,П—1
	а 4

Пространство ЬР(0(х)к+1) имеет над Р размерность т(к+1) и потому сос­ тоит ровно из цт(к+|)последовательностей. Число различных наборов (ао, Эк) элементов из <3 также равно цт(1с+1). Поэтому для доказательства теоремы доста­ точно показать, что любая последовательность вида (4) принадлежит Ьр(0(х)к+|) и различным наборам коэффициентов (ао,..., а^ е Р(к+1) соответст­ вуют различные последовательности вида (4).

Любая последовательность и, удовлетворяющая условию (4) при неко­

торых ао,... ,ак6 С|, есть сумма последовательностей и = ио + щ + ... +	где
для г е 0, к последовательность иг, задается равенствами

Введем обозначения а 0 = а, а, = а ч,...,ат_! = а 4 . Тогда по

определению 11

Отсюда и из равенств иг(1) = |1г^(ага ‘ ][ 1 е N 0-, пользуясь обоз­

начениями определения 9, получаем

и в силу и = ио + и) + ... + ик,

Г = 0 8 = 0

Теперь заметим, что (по приведенной в начале доказательства вспомо­ гательной теореме) а 0, ..., Ощ-1 - суть все различные корни в О неприводимого

над Р многочлена О(х), т.е. О(х) = (х - ао)-...-(х - ат-0, и каноническое разло­ жение над О многочлена 0(х)к+1 имеет вид 0(х)к+1 = (х - а0)к+1 (х - ат_1)к+1.

Поэтому из (5) и теоремы 8 следует, что и € Ьо(0(х)к+|). Так как, кроме того, и е Р°°ввиду (4), то и е Ьд(0(х)к+1)ПР°° = ЬР(С(х) ). Наконец, так как элементы ао,..., ат_1 е О попарно различны и отличны от нуля, то по теореме 8 система

	487
последовательностей	: 8 € 0, ш —1, г е 0,к | линейно независима над ().

Поэтому различным наборам коэффициентов (ао,..., а*) е (3(к+1) соответствуют различные последовательности вида (5).

Замечание 4. Из доказательства теоремы 10 вытекает следующий спо­ соб представления знаков ЛРП и е Ьр(С(х)к+1) в виде (4). Так как ие Ь<}((3(х)к+|), то и однозначно представляется в виде

т-1 к	______	__
и = ^ 2 Х га 8Г], где а8г е р ,8 € 0,т -1,		г е 0,к.	(6)
8=0г=0

Коэффициенты а^ в этом представлении находятся путем решения сис­ темы линейных уравнений над <3 (см. замечание 3). Из единственности пред­ ставления (6) и существования для и представления вида (5) следует, что коэф­

фициенты азГв (6) удовлетворяют соотношениям		г-
2	пт~1
*Чг ~ ^ 0 г ’ ^2г — **0г ’" , , я т -1 г	= ^0г	Г б О , к,

и искомые коэффициенты ао,..., а* в разложении (4) суть ао = аоо, &\ = ао1, ...,

вок. Указанные соотношения и представляют собой упомянутые в замеча­ нии 4 ограничения на коэффициенты а^ разложения (6) произвольной ЛРП и € Ь<)(0(х)к+*), которые накладываются условием и е Р00.

Пример 10. Пусть и - ЛРП над полем Р = 25 с характеристичес­

ким многочленом (х2 - 2х - 2)2 и начальным вектором и( 0,3 ) = (0, 0, 0, 1). Тре­

буется представить общий член этой ЛРП с помощью функции "след" и вычис­ лить и(37). Непосредственной проверкой убеждаемся в том, что многочлен С(х) = х2 - 2х - 2 не имеет корней в Р и потому неприводим. Пусть (3 = ОР(52) - минимальное поле разложения С(х) над Р и а е <3 - корень О(х). Тогда согласно теореме 10 общий член 11(1) ЛРП и однозначно представляется в виде

и(1) = 1г(аоа') + Пг^а').

Для отыскания коэффициентов ао, в этом представлении ищем коэф­ фициенты аоо, воь аю, ац е (3, удовлетворяющие равенству (6), которое в дан­ ном случае имеет вид:

и = а00а[,01 + а01а^,] + а10а[0] +

где а 5 = а 5 , а 3°3 = (...,015,...), а 3’3 = (...Да^.,...) для в е 0,1. Согласно замечанию 4 а<> = аоо, я/ =аоь Коэффициенты а51 находятся из системы ли­

нейныхуравнений

488

и(о,з)= а ^ а '01^ ас|а '11(о,з)+ а|0а '01(о,з)+а„а™(о,з)

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

1	0	1	0 ^	(я >
а	а			а оо
		а 5	а 5	а 01	0
а2	2а2	а 10	2а'°	а 10	0
У	З а 3	а 15	З а 15,	Ча П V	у

Составим расширенную матрицу системы

( \	0	1	0	0^
а	а	а 5	а 5	0
а2 2 а 2		а 10	2 а 10 0
к	З а 3	а 15	З а 15	К

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

г\	0	1	0	0^
0	а	а 5 - а	а 5	0
0 а 2		а 10 - а 6	2 а 10- а 6 0
,0	а 3	а 15 - а "	З а 15- 2 а " К

Повторяя ту же процедуру с 4-й и 3-й строками В, получаем

		489
{\	0 ,	1	0	0^
0	а	а 5 - а	а 5	0
0	0	а 10 - 2 а 6 + а 2	2 а ' ° - 2 а 6	0
,0	0	а 15 - 2 а 11 + а 7 З а 15 - 4 а 11 + а 7 Ь

Вычитая из 4-ой строки матрицы С 3-ю, умноженную на а 5, находим

1	0	1	0	0^
0	а	а 5 - а	а 5	0
0 0		а 10 - 2 а 6 + а 2	2 а 10- 2 а 6 0
	0	0	а 15 - 2 а 11+ а 7 К

Так как а - корень многочлена х2 - 2х - 2, то справедливы соотношения

а 2=2а+2	а 5=4а+2	а 10=За+1
а3=а+4 а6=3	а"=2а+1
а4=а+2а7=3а	а |5=4а+1>,

пользуясь которыми матрицу О можно записать в виде

Г1	0	1	0	0 >
0	а	Зос + 2	4 а + 2 0
0	0	2	а +1	0
	0	0	З а + 4

Так как (За+4) 1= а, то, вычитая из 3-й строки матрицы Э ее 4-ю стро­ ку, умноженную на а(а+1), получаем

г\	0	1	0	0	^
0	а З а + 2 4 а + 2			0
0	0	2	0	2 а + 3
ч0	0	0	З а + 4	1	)

490

Теперь, как нетрудно видеть, в исходной системе линейных уравнений выделяется подсистема

1 1 У а*004

.0 2 Чаюу

из которой находим аю = а + 4, аоо= 4а + 1 и ао = аоо = 4а+1. (Для проверки, заметим, что = (4а + 1)5 = 4 а 5 +1 = 4(4а + 2) + 1 = а + 4 = а,0). Отсюда для отыскания переменных аю, ац получаем следующую систему

а	4 а + 2	г- (З а + 2 )(а + 4)
, 0	З а + 4	1

Решая ее, находим ац = (За+4) 1= а, ао1 = а ‘(1 - а(4а + 2)) = За 1= 3(3а + 4) = 4а + 2 = а 3, и ао1= 4а+2.

Окончательно получаем, что искомое представление знаков ЛРП и име-

ет вид

и(1) =1г((4х+1).х‘)+Нг((4х+2).х‘)

для I е N0 .

Теперь значение и(37) можно вычислить следующим образом.

Так как а24= а 25-1 =1, то а37 = а 13 = а 3а 10 = (а+4)(За+1) = 4а. Отсюда и=1г((4а+1)-4а)+371г((4а + 2)- 4а) = =1г(((4а+1) + 2(4а + 2))-4а) = 1г(3а2) = 1г(а +1) = *г(а) + 1г(1).

Так как а - корень неприводимого многочлена х2 - 2х - 2, то по теореме 9 (в) 1г(а)= 2 и 1г(1)=2. Отсюда и (37) = 4.

. Замечание 5. Теорема 10 позволяет вычислять с помощью функции «след» знаки линейной рекурренты не только с примарным, но и вообще с лю­ бым характеристическим многочленом Р(х), таким, что Р(0)*0. Для этого до­ статочно найти каноническое разложение Р(х) и представить исходную ЛРП в виде суммы ЛРП с примарными характеристическими многочленами, пользу­ ясь теоремой 6.