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

471

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

екР=Ск1и1+...+сктит.

Но тогда для матрицы С=(с^) размера шхщ справедливы равенства

С 1>

= Е

етг(0,...т-1)

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

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

пространства ЬР(Р) равна степени многочлена Р(х).

Умножение последовательности на многочлен.

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

хк-и=у,

где у(1)=и(1+к), для 1е N0.

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

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

т

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

к=0

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

А(х)и = ^	ак (хк • и) .
к=О		*
	т
То есть А(х)и=у/, где	н>(7) = ^ а к • и{1 + к)	для 1еМ0 .
	*=о

Несложно доказывается Утверждение 4. для^любого многочлена Р(х)€К[х]

Ьк(Р)={ие К®: Р(х)и=(0)}.

У

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

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

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

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

472

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

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

А(х) = ^ а кхк , В(х) = 2 Ь

к>0

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

Л

(А(х)В(х))и= 2 ак ^ х к+л	-и =	]Г а кх к( Ъ ^ - и ) =
к,]*>0	)	к,]>0

= 2 > к Х к(В(х)и) = А(х):(В(х)-и)).

к>0

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

Для унитарного многочлена Р(х)еК.[х] степени т>0 через ер обозначим

ЛРП из Ьк(Р) с начальным вектором ер( 0, т	- 1 )=(0,0,...0,е).
Справедлива /11/	1

Теорема 2. Пусть Р(х)= хт-Гт_1Хт_| -...-Го еК(х), т>0. Тогда для любой

ЛРП иеЬк(Р) существует единственный многочлен ф(х)еК.(х) степени меньшей ш такой, что

и=ф(х)- ер

иэтот многочлен имеет вид

т- 1

ф(х)=и(0)хт~1+ ]Г (и(к)-Гт_1и(к-1)-.. .-Гт_ки(0))хт“1_к.

. к=1

Замечание 1. В случае когда К.=Р - поле, теорема 2, по сути дела, утве­ рждает, что Ьр(Р) - подпространство пространства Рх, не только инвариантное относительно преобразования ст, определяемого условием: для любого ие Рх ст(и)=х-и, но и циклическое относительно ст, причем ер - вектор, порождающий подпространство Ьр(Р).

Определение 6. Многочлен ф(х), удовлетворяющий условию и=ф(х)- ер

называется генератором ЛРП и относительно ее характеристического многочлена Р(х).

473

Определение 7. Характеристический многочлен ЛРП и, имеющий наи­ меньшую возможную степень, называется ее минимальным многочленом, а его степень называется рангом ЛРП и и обозначается через гап§ и.

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

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

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

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

Теорема 3. Любая ЛРП и над полем Р имеет единственный минималь­ ный многочлен 0(х)еР[х], и он удовлетворяет равенству

Апп(и)=Р[х]0(х).

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

. ЛРП и, на который делится любой другой ее характеристический многочлен. Следовательно, О(х) - единственный минимальный многочлен ЛРП и.

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

Теорема 4. Для любого унитарного многочлена 0(х)еК.[х] и любой по­ следовательности иеК00 следующие утверждения эквивалентны

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

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

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

Н(х)=С>(х) 0(х)+А(х), с!е§А(х)<ёе§0(х).

Тогда А(х)еАпп(и), так как Н(х)и=О(х)и=(0). Следовательно, С 1 ( х ) = 0 ( х ) + А ( х ) - унитарный многочлен из Апп(и) той же степени, что и О(х),

то есть 0](х) - минимальный многочлен ЛРП и. Но тогда ввиду условия (а)

С1(х)= О(х), то есть А(х)=0 и Н(х)€ К[х] 0[х]. Импликация (б)=>(а) доказывае­

тся так же, как и в теореме 2. Несложно доказывается

Утверждение 5. Пусть Р(х)еК.(х) - унитарный многочлен степени т>0, иеЬк(Р) и

474

и( 0, т - 1 )=(0,0,... ,а), где ае К - элемент, не являющийся делителем нуля. Тогда Р(х) - единственный минимальный мцогочлен ЛРП и.

Следствие. Для любого унитарного многочлена Р(х) € К[х]

Апп(е р )=К[х]-Р(х).

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

а^®=(к) а ',1еМ (

называется биномиальной последовательностью порядка к+1 с корнем а . Утверждение 6. Если элемент а е К. не является делителем нуля, то

а ^ -ЛРП с единственным минимальным многочленом <3(х)=(х-а)к+1. ДОКАЗАТЕЛЬСТВО. Докажем индукцией по к включение

а^ е Ьц |(х - а )к+1]. При к=0 оно очевидно. Пусть к>0 и

ае ЬК((х - а )к ). Тогда используя известное равенство

'1+ П С Л	( I }	Гк1
=	1 к - П	, получаем (х-а) а 1 ]=у, где
к

а 1 = а -а ^ к'^(1),

МГ к-1 1

,= & • а 1 \ Отсюда, пользуясь предположением индукции имеем (х -а)к+1 • = а • (х - а )к • сДк’^ = (0).

Остается заметить, что оДк^(( 0,1 ) = (0,...,0,ак )) , и так как а к- не делитель нуля в К, то по утверждению 5 характеристический многочлен (х-

а)к+1 ЛРП а ^ является ее единственным минимальным многочленом. Простой способ вычисления минимального многочлена ЛРП над полем

дает

Теорема 5. Пусть и - ЛРП над полем Р с характеристическим многоч­ леном Р(х) и генератором ф(х). Тогда

475

(а) М.(х)=

Р(Х)

;

(Р(х)Жх))

(б)если у=Н(х)-и для некоторого Н(х) е Р[х], то

М,(х ) = ----- М “(х)

(Н (х),М и(х))

ДОКАЗАТЕЛЬСТВО, (а) По определению генератора справедливо ра­

венство и=ф(х)-ер, и так как по следствию утверждения 5 (х) = Р(х), то (а)

следует из (б).

(б) Достаточно заметить, что по теореме 2 для любого А(х)еР[х] спра­ ведливы соотношения

А(х)-у=(0) <=>А(х)Н(х)и=(0) о	- ■|А(х).
	(Н (х),М и(х))

Следствие. Минимальный многочлен ЛРП и€Ьр(Р) равен Р(х) тогда и только тогда, когда ее генератор относительно Р(х). взаимно прост с Р(х). В час­ тности Р(х) является минимальным многочленом для любой ненулевой ЛРП из Ьр(Р) тогда и только тогда, когда Р(х) неприводим над Р.

Для линейных рекурент кольцом над теорема 5(а) может быть обобщена следующим образом.

Утверждение 7. Если и - ЛРП над кольцом К с характеристическим многочленом Р(х) и генератором ф(х), то

Аип(и)={А(х) € К[х]: Р(х)|А(х) ф(х)} ДОКАЗАТЕЛЬСТВО. Так как и=ф(х)-ер, то по следствию утверждения 5

А(х)и=(0) о А(х) -ф(х) -ер о Р(х)| А(х) -ф(х).

Соотношения между семействами ЛРП с различными характеристиче­ скими многочленами.

Утверждение 8. Для любых унитарных многочленов Р(х),0(х)€ К[*]

(Ьк(0 )е Ь к(Р))«(0(х)|Р(х)).

ДОКАЗАТЕЛЬСТВО. Пусть С(х)|Р(х). Тогда

иеЕк(О) => О(х) и=(0) => Р(х) и=(0) => иеЬя(Р).

476

Пусть Ьа((3)с: Ьа(Р). Тогда е°е ЬК(Р), Р(х)-ес=(0) и по следствию утверждения 5

О (х) | Р (х).

Определение 10. Многочлены Р (х), О (х) € К. [х] называют взаимно простыми, если К.[х]-Р(х)+К.[х]0(х)=К[х], т. е. А(х)Р(х)+В(х)С(х)=е для неко­ торых А(х), В(х)еИ[х]. В этом случае пишут (Р (х), О (х))=е.

С использованием этого определения несложно, аналогично тому как это делается для многочленов над полем, доказывается

Утверждение 9. Для любых многочленов Р(х), О(х), Н(х)еК.[х] справедливы импликации

(а)((Р(х), 0(х))=е, (Р(х), Н(х))=е) => (Р(х), О(х) • Н (х))=е;

(б)((Р(х), <3(х))=е, Р(х) | О(х) • Н(х)) => Р(х) | Н (х);

(в) ((Р(х),0(х))=е, Р(х) | Н(х), О(х) | Н(х)) => Р(х)0(х) | Н(х). Теорема 6. Пусть Р0(х),Р|(х)еК.[х]-унитарные взаимно простые

многочлены и Р(х)=Р0(х)-р1(х).

Тогда

Ьк(Р)=Ья(Р0) + Ы Р .)

Если К. - поле и последовательность иеЬк(Р) представлена в виде и=ио+и1, и8еЬк(Р8), зе 0,1, то

(Ми0(х),Ми1(х))=е, Ми(х)= Ми0(х)-Ми1(х).

ДОКАЗАТЕЛЬСТВО. По утверждению 8 Ьк(Р5)с ЬК(Р) для 8е 0,1 и по утверждению 2

	Ь ^ з Ь ^ + ЬаСРО
Так как по условию Ао(х)Р0(х)+А1(х)р1(х) =е для подходящих
Ао(х),А!(х)еК.[х], то	любая последовательность иеЬк(Р) представляется в
виде
и=ио+иь	__
гдеи8=А1_5(х) р1_8(х)-и	для §€0,1.
Очевидно, что	Р5(х)-и5= А1_5(х)-Р(х)-и=(0), т. е. и8€Ьк(Р8)- Отсюда и из

Ьа(Р) з Ьк(Ро) + Ек(Р0 следует равенство Ьа(Р)=Ек(Ро) + ЬкСРОЕсли иеЬк(Ро)оЕа(Р|), то Р8(х)и=0 для зе 0,1, и потому в приведенном выше равенс­ тве и=ио+и1 выполняются соотношения: ио=и|-(0), то есть и=(0). Требуемое в

теореме 6 равенство доказано.

477

Если К. - поле, и и= и0+и1, и8е Ьк(Р5)> 8<= 0,1, то по теореме 3

М и> (х)|Р5(х), и потому (М ио (х), М и( (х)) =е.

Теперь для доказательства равенства Ми(х)=Мио(х)-Ми|(х) остается за­ метить, что М и^(х) есть минимальный многочлен вектора и5е Ьк(р) относи­

тельно линейного преобразования а=а| ЬК(Р) (см. замечание 1), и воспользо­ ваться известными утверждениями о минимальных многочленах векторов от­ носительно линейных преобразований векторных пространств.

Для ЛРП над полем первое утверждение теоремы 6 может быть сущест­ венно усилено.

Теорема 7. Для любых унитарных многочленов Р(х) и О(х) над по­ лем Р справедливы равенства

ЬР(Р) п ЬР(0)= Ьрф), где Э (х)=(Р (х), О (х));,	(1)
ЬР(Р) + ЬР(С)= ЬР(Н), где Н(х)=[Р(х),С(х)].

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

Из утверждения 8 следует также включение ЬР(Р)+ЬР(0) с ЬР(Н).Остается заметить, что по следствию утверждения 3 и в силу (25)

(Пт (Ьр(Р)+ЬР(0)) =сПт ЬР(Р)+(Пт ЬР(0)-Л т(Ь Р(Р) п ЬР(0 » =

=Пе§ Р(х)+й?е# С(х)-с1е% Б (х)=Пе§ Н (х)=еПт Ьр(Н). □

Биномиальный базис пространства ЛРП над полем.

Все рассмотренные до сих пор базисы пространства Ьр(Р) не давали способов представления общего члена 11(1) произвольной ЛРП иеЬР(Р) в виде просто вычисляемой и записываемой явной формулой функции от параметра 1.

Опишем важный частный случай, когда такой способ существует.

Теорема 8. Пусть многочлен Р(х) е Р [х]	раскладывается над по­
лем Р на линейные множители и имеет каноническое разложение вида
Р(х) = ( х - а , ) к‘+| • ... • ( х - а г)кг+1, а 8 * 0 , к8 > 0 ,	д л я з е 1 ,г .	(2)

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

(см. определение 9).

ДОКАЗАТЕЛЬСТВО. По теореме 6 пространство Ьр(Р) есть прямая су­ мма подпространств

ЕР(Р)=Ьр((х-а1) к'+1)+.. .+ЬР((х -а г) к'+1).

Остается доказать, что система последовательностей

а 5[01,а 5111,...,а 8[к81 есть базис пространства Ьр((х - а 5)к‘+1). Включения

а 8[11е Ь р ( ( х - а 5)к!+1) для 1е 0,к8 следуют из утверждения 6. Теперь достато­

чно заметить, что система из к5 +1 векторов длины к5 +1:

ад0Н0’к8)==(е

а[$1](<зЛГ)= (0, е,*,-••,*),

а ^ 8](0,к8)= (0,....,0,е)

линейно независима над Р и воспользоваться утверждением 3.

Следствие 1. При условии (2) для каждой ЛРП иеЬр (Р) существует единственный набор коэффициентов

>®20»”,»^2к2’"*>^йсг ^ ^

такой, что для каждогот е N выполняется равенство

479

'О	(\	\
и(1) —^10^1 а 1 а	+... + а1к,	ос| +
	чк.у
+ а20а'2 +	+ а2к, ГХ ла 2 +		(3)
		Чк2У
+ аюа г +	+ а	сх‘
	' ГЧ	кг У
ДОКАЗАТЕЛЬСТВО. Нужные коэффициенты а 5>1			суть коэффициенты

в разложении вектора и е ЬР

5=1 1=0

по базису

а1[01,а1[11,...,а111с,],

а2т,агт, .... а ™ ,

а г т , а г 1\ . . . , а Тм .

По разложению (3) последовательности и можно легко построить ее минимальный многочлен и найти гап§ и. Мы рассмотрим здесь наиболее прос­ той и важный частный случай.

Следствие 2.	Если оц,..., а г - попарно различные элементы Р\0, то
для любых аь а, е Р	последовательность и е Г элементов вида
	и(1) = а ,а |1+ ... + ага ’г*	■	•

есть ЛРП с характеристическим многочленом Р(х)= (х-а| )•...• (х-аг) При этом ранг последовательности и равен числу ненулевых коэффициентов среди аь ...,

8	8	----
Зги Ми( х ) = ( х - а , )	1 - ... - ( х - а ^ ) г,гдедля з е 1,г
	[1, если	а8 ф 0,
	е 5 = 10, если	а. = 0.

480

ДОКАЗАТЕЛЬСТВО. Включение и е Ь&(Р) очевидно. Тогда Ми (х) | Р (х), т. е. М„ (х) - произведение некоторых одночленов из (х-а])-...-(х-аг)

. Упрощая обозначения, допустим, что

М и (х) = ( х - а 1) - . . . - ( х - а 1), 1 < 1 < г .

Тогда по следствию 1 существуют С1 ,..., с, е Р такие, что

V 1 е]Ч0 : и(1) = с ,а |, +... + с,а |.

Отсюда, пользуясь единственностью представления (3), получаем аг=С1,..., а,=сь а,+1 =.. .=аг=0. Остается заметить, что все коэффициенты сь ...,

с, отличны от нуля. Действительно, если например с, =0, то иеЬР((х-оц)-...-(х- Оц)), что противоречит допущению о виде Мч(х).

Замечание 2. Пусть в обозначениях теоремы 8 т=с1е§ Р(х)= (к!+1)+...+ (кг+1). Тогда каждая ЛРП ие ЬР (Р) однозначно определяется своим начальным вектором и (0, ш —1), и для нахождения коэффициентов ам в раз­

ложении (3) достаточно составить систему ш линейных уравнений с ш неизвес­

тными {х5 4 ; 5 € 1, г, I € 0, к8}, которая в векторной форме имеет вид

и(0, ш -1 ) = Х 8=1 Х Ь о х-81а з](0, т -1).

Однозначная разрешимость этой системы следует из линейной незави­

симости системы векторов | а ^ ( 0 , т - 1 ) :8,е 1,г, 1	е 0 , к 8|
(см. теорему 8 и утверждение 3).
П р и м е р е . Пусть и - ЛРП над полем Р = 2 5.	с характеристическим

многочленом Р(х) = х - 2 х + х + З х - 2 и. начальным вектором

и(0,5 )= (0, е, е, 0, 3, е, е). Требуется найти и (1986).

Перебором элементов поля Р убеждаемся, что многочлен Р(х) имеет в Р корни а, = е, а 2 = 2е, а 3 = З е, и его каноническое разложение над Р .имеет вид

Р(х) = (х - е)3 • (х - 2е)2 • (х - Зе).