Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)
.pdf
492
тогда и только тогда, когда
\> А (и ), Т(и) 11.
ДОКАЗАТЕЛЬСТВО. Введем, для краткости, обозначения: А(и)=Хо, Т(и)=10. Пусть М - множество всех различных элементов из П, встречающихся в последовательности и. Так как и - периодическая последовательность, то М - конечное множество: |М| < А.0+1оВыберем произвольно поле Р такое, что |Р| > |М|, зададим инъективное отображение ^:М—>Р и определим последователь
ность и еР°° условием и 0)=^(и(1)) для 1еЬ[о. Ввиду инъективности отображе ния %очевидно, что для фиксированных ХеЫ0и 1еИ условие V 1 > X: и(1+1) = 11(1) равносильно условию
хх(х‘-е) = (0).
Отсюда и из условия теоремы следует, что и - периодическая последо
вательность, причем Т( и )=1о, А( и )=Л,0 и нам достаточно доказать, что указан ное условие равносильно условию
X > А,о, 1о 11-
Так как по определению 13
ххо(х'°-е)й=(0)
и из X > А-о, 1о И следует, что хк0(х10-е) | хх(х‘-е), то из X > Х0, То 11 следует хх(х!-е) = (0).
Наоборот, допустим, что параметры ХеИо, ЦИ удовлетворяют условию хк(х'-е) = (0), и докажем выполнение условий А > Я0,1о 11 - Покажем, что спра ведливо равенство
(хх(х*-е), ххо(х'°-е))=хк(х(1-е), где к=тт{Х, А.о}, <1=(1,1о).
Действительно, очевидно, что (хк(х‘-е), хХ0(х10-е))=хк(х1-е, х,0-е) и так как по определению 14 I > То, то х1-е=х'~*°(хю-е)+(хм0-е), откуда (х‘-е, х*°-е)=(х*' *°-е, х‘°-е). Теперь исследуемое равенство легко доказывается индукцией по Жо. •
493
Так как многочлен хк(х‘|—е) есть линейная комбинация многочленов
х\х'-е) и хк0(х'°-е), то из хк‘(х*-е) = (0) и равенства ххо(х*°-е) и =(0) следует, что
хк(хё-е)и=(0).
Отсюда по определению параметра *о=Т(и) следует, что б > кь а так как
б=(1,10) 14о, то (1=1о, 1о 11 и справедливо равенство х'(х<0-е)и=(0). Но тогда по определению параметра Хо=Л(и) справедливо неравенство к > Х0, то есть верны
условия X > Хо, *о 11 • Теорема доказана.
С ледствие 1. Если и - периодическая последовательность, то Л(и) есть наименьшее А.еМ0, для которого существует со свойством
V 12 X: и(1+1) = и(1).
С ледствие 2. Если и —периодическая последовательность над коль
цом К., то для любого многочлена Н(х)еК[х] последовательность у=Н(х)-и - также периодическая, причем Л(у) < А(и), Т(у) | Т(ц).
ДОКАЗАТЕЛЬСТВО. Достаточно заметить, что если Л (и )= А .о , Т(и)=10,
то
х*°(хв-е)-у = Н(х)ххо(х'°-е)-и=(0).
В качестве важного приложения теоремы 11 докажем
У тверж дение 11. Если и,уеК.°°, - периодические последовательно
сти, то \у = и+у периодическая последовательность и
Л(ш) < шах{Л(и), Л(у)}, Т(\у) | [Т(и), Т(у)]. При этом
(а) если Л(и)*Л(у), то
Л(\у)=тах{Л(и), Л(у)};
(б) если (Т(и), Т(у))=1, то
Т(*г)=[Т(и),Т(у)];
(в) если и и у - ЛРП, для которых можно указать взаимно простые хара ктеристические многочлены, то справедливы равенства Т(\у)=[Т(и), Т(у)] и
Т(ш)=[Т(ц),Т(у)].
494
ДОКАЗАТЕЛЬСТВО. Пусть Я,=шал:{Л(и), Л(у)}, Г=[Т(и), Т(у)]. Тогда по теореме 11
хх(х'-е)и=(0) и хх(х‘-е)у=(0)
и, следовательно, хх(х*-е)\у=(0). Отсюда, опять по теореме 11, следуют соотношения
Л(\у) < шах{Л(и), Л(у)}, Т(лу) | [Т(и), Т(у)].
(а). Если, например, Л(и) < Л(у), то Х=Л(у). Допустим, что Л(\у) < X,. То гда многочлен хх_1(х‘-е) аннулирует последовательности и и \у, а значит и по следовательность у=\у-и. Но тогда по теореме 11 Л(у) < Х-1, что невозможно. Следовательно, Л(\у)=Х, т. е. верно равенство Т(\у)=[Т(и), Т(у)].
(б). Пусть (Т(и), Т(у))=1 и Т(\у)=т. Заметим, что [т, Т(и)]= т-к, где к=Т(и)/( т, Т(и)) > 1, и так как т | тк и Т(и) | тк, то по теореме 11 хх(хкт-е)\у=(0), хх(хтк-е)и=(0). Но тогда хх(хтгк-е)у=(0), и по теореме 11 Т(у) | тк, а поскольку (Т(у), к)=1, то Т(у) | т. Аналогично доказывается, что Т(и) | т. Следовательно, Т(и)-Т(у) | Т(\у). Теперь равенства Т(\у)=[Т(и), Т(у)] следует из соотношений
Л(\у) < шах{А(и), Л(у)}, Т(ху) | [Т(и), Т(у)].
(в). Пусть иеЬк(Р), уеЬ а(С) и (Р(х), 0(х))=е. Тогда \уеЬк(Р-С) и Ек(Р-С)=Ьк(Р)+Ьк(0). Отсюда, учитывая, что для любых А^еИо, 11 еЫ справед
ливы соотношения
хХ1(х11-е)\у=хХ|(х*1-е)и+хХ|(х‘|-е)у, хХ1(х“-е)иеЬк(Р), хХ1(х*'-е)уеЬа(0)
получаем:
V Х\ еИ0, 11 еИ : (хХ1(х‘'-е)\у=(0)) <?>(хХ|(х"-е)и=(0), хХ1(х*'-е)у=(0)).
Теперь соотношения Л(\у) < шах{Л(и), Л(у)}, Т(\у) | [Т(и), Т(у)] и ра венство Т(\у)=[Т(и), Т(у)] следуют из теоремы 11. Утверждение доказано.
Определение 14. Периодическая последовательность и над коль цом К называется чисто периодической, если Л(и)=0 и вырождающейся, если и=(и(0),..., и(Х-1), 0, 0,..., О,...) для некоторого А.еМ0.
Очевидно, что и - чисто периодическая последовательность тогда и то лько тогда, когда иеЬк(х'-е) для некоторого 1еИ, и и - вырождающаяся после довательность тогда и только тогда, когда иеЬк(хх) для некоторого Х.еИо.
Единственная одновременно чисто периодическая и вырождающаяся последо вательность - нулевая: Л((0))=0, Т((0))=1.
Теорема 12. Любая периодическая последовательность ие К00 одно значно представляется в виде суммы
495
1 1 = 1 1 0 + 4 1 ,
где иввырождающаяся, и! - чисто периодическая последовательности. При этом
Л(и)=Л(ио), Т(и)=Т(и,).
ДОКАЗАТЕЛЬСТВО. Пусть А(и)=3., Т(и)=1. Тогда иеЬк(хх(х'-е)). Из очевидного соотношения (х, х*-е)=е в силу утверждения 9 (а) следует соотно шение (хх,х*-е)=е. Отсюда, пользуясь теоремой 6, получаем, что
Ьк.(хх(х,-е))=Ьк(хх)+Ь[1(х'-е),
и последовательность и единственным образом представляется в виде
и=ио+иь иоеЬк(хх), и1еЬк(х'-е).
Это и есть искомое разложение и=ио+и1. Равенства Л(и)=Л(ио), Т(и)=Т(и1) легко следуют из утверждения 11.
Пусть имеется еще одно разложение и=у0+У|, где у0, VI - соответственно чисто периодическая и вырождающаяся последовательности. Тогда по утверж дению 11 Л(у0)=Л(и)=Я., Т(У|)=Т(и)=1. Следовательно, УоеЬк(хх), V, еЬа(х'-е) и ввиду Ьк(хх(х*-е))=Ьк(хх)+Ьк(х‘-е) справедливы равенства Уо=ио, У1=и1. Теорема
доказана.
Замечание 6. На практике, для представления последовательности иеЬк(хх(х*-е)) в виде и=ио+и1, достаточно подобрать кеN такое, что 1к > X. Тог да х,кчо=(0) и из указанного вида и следует, что х'Ч^х'Ч^и,. Теперь последова тельность ио находится из равенств ио=и-и1=и-х,ки. Например, для последова
тельности
и=(00 2 2 1 3 1 2 0 3 1 20 ...Ч
над 24 справедливы соотношения Л(и)=^=5, Т(и)=1=4,1-2=8 > X. Следо вательно,
\11=х8-и=(0 3 12 0 3 12...),
ио=и-и,=(01 1 0 1 0 0 0...).
496
Периодические многочлены. Периодичность ЛРП над конечным кольцом.
Для кольца К через К* обозначим множество (группу) всех его обратимых элементов.
Заметим, что если К - произвольное кольцо, то не любая ЛРП над К периоди чна, т. е. обращение утверждения 10 неверно. Простейший пример:
ЛРП 1^ (0, 1, 2, 3, ...)еЬ 2((х-1)2).
Однако, если К - конечное кольцо, то обращение утверждения 10 верно. Дока зательство этого факта и методика расчета периода ЛРП над конечным кольцом опи раются на следующие результаты.
О пределение |
15. ^Многочлен р(х)е К[х] назовем периодическим, если суще |
|
ствуют параметры Хе1Чо, |
такие, что |
|
Р(х)|хЧх'-е). |
|
|
При этом наименьшее |
для которого существует А,еЫ0, удовлетворяющее |
|
условию Р(х) | хх(х - е ), обозначим через Т(Р) и назовем периодом многочлена Р(х), а наименьшее такое, что Р(х) | хх(хТ(р)-е) обозначим через А(Р). Унитарный пери одический многочлен Р(х) со свойством Л(Р)=0 назовем регулярным.
Связь введенных понятий с понятием периодической последовательности устанавливает
У тверж дение 12. Унитарный многочлен Р(х)еЯ[х] является периодическим тогда и только тогда, когда периодична ЛПР ер ё Ь&(Р). Если Р(х) - периодический многочлен, то
Л(Р)= Л(ер), |
Т(Р)=Т(ер) |
|
|
и любая ЛПР иеЬа(Р) есть периодическая последовательность, для которой |
|||
Л(и) < Л(Р), |
Т(и) | Т(Р). |
|
|
ДОКАЗАТЕЛЬСТВО. Так как по следствию утверждения 5 Ллл(ер)=К[х]-Р[х], |
|||
то |
|
|
|
У^еЬГо, |
(х \х ‘-е)еР=(0)«Р(х) |
I хх(х1-е). |
. |
Отсюда следуют первая часть утверждения 12 и соотношения А(Р)= А(ер), |
|||
Т(Р)=Т(ер). Пусть иеЬя(Р). Тогда Р(х)и=(0), и так как |
|
||
|
Р(х) | хЛ(р)( хТ(р-е), |
то хЛ(р)( хТ(р)-е)и=(0). |
|
Следовательно, и - периодическая последовательность, и по теореме 11 верно Л(и)<Л(Р), Т(и) | Т(Р).
497
Следствие 1. Если Р(х) еК[х] - унитарный периодический многочлен, то
УЯ-еЫо, |
(Р(х) | (х\х'-е)) о (X > Л(Р), Т(Р) | г). |
Д01САЗАТЕЛЬСТВ0. Достаточно воспользоваться соотношениями:
УХеЫ0, |
(х^(х'-е)еР=(0)<»Р(х) | х^х'-е); |
А(Р)=А(ер), |
Т(Р)=Т(ер) |
и теоремой 1 1 . |
|
Следствие 2. Если Р(х), О(х) еК[х] унитарные периодические взаимно прос
тые многочлены, то Н(х)= Р(х)0(х) - периодический многочлен, причем
Л(Н)=/иах(Л(Р),Л(С)}, Т(Н)=[Т(Р),Т(С)].
ДОКАЗАТЕЛЬСТВО. Пусть >1=тах{Л(Р),Л(С)}, 1 =[Т(Р),Т(0)]. Тогда по следствию 1 многочлен х \ х 1-е) делится на Р(х) и О(х), и по утверждению 9(в) Н(х) |
(х^х'-е)). Таким образом, по определению 15 Н(х) - периодический многочлен, и по следствию 1 Л(Н) < X и Т(Р) | Т(Н), Т(О) | Т(Н), т. е. * | Т(Н).
Замечание 7. Если К - произвольное бесконечное кольцо, и Р(х), О(х) еК[х]
унитарные периодические, но не взаимно простые многочлены, то многочлен Н(х)= Р(х) С(х) может быть не периодическим. Например, если К=(2, Р(х)=0(х)=х-1,
то Н(х)=(х-1)2- многочлен с кратным корнем 1 и потому о не делит ни одного из мно
гочленов х -1, Иная картина имеет место, если К - конечное кольцо.
Теорема 13. Пусть Р(х) - унитарный многочлен степени т>0 над конечным
кольцом К. Тогда
(а) Р(х) - периодический многочлен, причем если | К | т >2, то
Л(Р)+Т(Р) < | К | т-1;
(б) Р(х) - регулярный многочлен в том и только том случае, если Р(0)еК*.
ДОКАЗАТЕЛЬСТВО, (а) Рассмотрим факторкольцо 8=К[х]/Р(х) и последо вательность над 8:
[е]р,[х]ь ...,[х;]р,....
Так как 3 - конечное кольцо: 18 1= | К | т - то в указанной последовательности
есть повторения, т. е.
498
[хх]р = [ хх+,]р
для некоторых |
1е1Ч. Но это равенство, очевидно, эквивалентно условию |
Р(х) | х\х'-е).
Следовательно, Р(х) - периодический многочлен. Более того, из следствия утверждения 12 и равносильности условий [хх]Р = [хх+1]Р и Р(х) | хх(х*-е) следует, что А(Р)+Т(Р)=к - наибольшее натуральное число, такое, что элементы кольца 8
|
[е]Р,[х]Р, ...,[хкч]Р |
||
попарно различны. Поэтому всегда |
А(Р)+Т(Р) < 18 1+ 1Я | т. |
||
Покажем, что если |
| 8 | >2, |
то к < I 8 1- |
1. Допустим, что к> | 8 1- 1. Тогда |
к= | 8 1 и, и так как элементы |
[е]Р,[х]Р, .. .,[хк_1]Р |
попарно различны, то |
|
8 ={[е]Р,[х]Р...,[х]к-1Р}.
Поскольку [0]Ре8, то из последнего равенства для 8 следует, что [0]Р = [х]к_1, [х]Р - делитель нуля в 8 и [е]Р - единственный обратимый элемент в 8. Но
[е-х]Р- также обратимый элемент в 8, поскольку [е-х]Р*[е+х+...+хк"1]Р=[е-хк]Р=[е]Р. Следовательно [е-х]Р=[е]Р , [0]Р = [х]Р и ввиду равенства 8 = {[е]Р,[х]Р, ...,[х] Р} име ем 8={[е]Р, [0]Р }, т. е. | 8 | = 2, что противоречит условию.
(б). Если Р(х) - регулярный многочлен, То х Т(р)-е=Р(х)*С(х) для подходящего С(х)еЯ[х]. Но тогда Р(0)(-С(0))=е и поэтому Р(0)еЯ*. Наоборот, так как Р(х) имеет вид Р(х)-Р(0)+х-11(х), то из условия Р(0)еЯ*, очевидно, следует, что (Р(х),х)=е, и по
утверждению 9(а) |
(Р(х),х?1)=е, для любого |
Тогда так как Р(х) | хЛ(р)*(х т(р)~е), то по |
утверждению 9(6) |
Р(х) | х Т(р)-е, т.е. Р(х) - регулярный многочлен. |
|
Следствие. Если и - ЛРП порядка т над конечным кольцом К и |К|т >2, то
А(и)+Т(и)<|Я|т -1.
ДОКАЗАТЕЛЬСТВО. Если иеЬк(Р ), бе§ Р(х)=т, то нужное неравенство сле дует из А(и) < А(Р), Т(и) | Т(Р) и А(Р)+Т(Р) < | Я | ш-1 (см. теорему 13).
Замечание 8. При условии |Я|т=2 существует единственный пример, опровер
гающий неравенство Л(Р)+Т(Р) < | Я | т-1 и последнее следствие: Я=2,2, Р(х)=х, и=(1,0,0,...). В этой ситуации Л(Р)=Л(и)=1 и Т(Р)=Т(и)=1.
499
Вычисление периода и длины подхода ЛРП над конечным полем.
Прежде всего сведем поставленную задачу к изучению минимального многоч лена ЛРП.
Утверждение 13. Если и - ЛРП над конечным полем, то А(и)=А(Ми(х)), Т(и)=Т( Ми(х)).
ДОКАЗАТЕЛЬСТВО. Достаточно заметить, что в силу теоремы 3
V ХеЫ0, ^ : (хх-( х'-е)-и=(0))<» (М„(х) | х^(х'-е)). ■
Описание параметров А(Р) и Т(Р) для произвольного унитарного многочлена Р(х) над конечным полем сводится к построению его канонического разложения и вы числению периода неприводимых сомножителей. Пусть Р=ОР(я), я=рп, р - простое.
Для произвольного Р(х)еР[х] определим параметр О(Р) как наименьшее общее кратное (НОК) порядков всех ненулевых корней Р(х) в его поле разложения над Р и положим
0(Р)=1, если Р(х)=хк , к еК
/
Утверждение 14. Если Р(х)еР[х] - регулярный неприводимый многочлен степени т , то
1) Т(Р)=0(Р); 2) Т(Р) | ят —1 и Т(Р) не делит многочлены (як- 1 ) для к е{1,2,...,т-1};
3) в частности, (Т(Р),р)=1.
ДОКАЗАТЕЛЬСТВО.
*Пусть (^-минимальное поле разложения Р(х) над Р.
Тогда (3=ОР(ят) (по известным утверждениям описывающих строение простых
расширений полей), и если а-корень Р(х) в С>, то 0(Р)=огс1 а (следствие утверждений описывающих строение простых расширений полей). Так как Р(х) | хТ(р)-е, то ат(р)=е и О(Р) | Т(Р). С другой стороны, а0(р)=е и (Р(х),х0(р-е)*е. Поскольку х0(р)-е е Р[х] и Р(х) неприводим над Р,отсюда следует, что Р(х) | х0(р)-е, т.е. Т(Р) | О(Р) и Т(Р)=0(Р).
Т.к. а е (3*, то отй а | ят-1, т.е. Т(Р) | ят-1. Наконец, если . Т(Р) | як-1, где 1<к<т, то
кк
а 4 = в и а = а , что известным утверждениям описывающих строение прос
тых расширений полей. Доказательство окончено.
Из пункта 2) утверждения 14 вытекает следующий способ вычисления периода регулярного неприводимого многочлена Р(х) е РГх1 степени т>0.
1.Перебрать все делители 1 числа дт-1, не являющиеся делителями чисел
Я- 1 , я ш-1.
2.Для каждого выбранного ( проверить условие
х =е (той Р(х)).
Наименьшее из таких 1 , для которых это условие выполнено, есть Т(Р).
500
Пример 11. Вычислим период многочлена Р(х)=х4+х+1 над Р=Ъ2. Так как Р(х) неприводим, то можно применить описанный выше алгоритм. Поскольку
24—1=15=3*5 и 3 122-1, то нужно проверить условие х=е (той Р(х)) лишь для {5,15}. Так как х4=х+1 (той Р(х)) и хV 1 (той Р(х)). Следовательно, Т(Р)=15.
Теорема 14. Если Р-СР(ц) - поле характеристики р, унитарный многочлен Р(х)еР[х] имеет каноническое разложение
Р(х)=х' с 1(х)>|
и
к=тах{к! ,...к5}> то справедливы равенства
Л(Р)=1, Т(Р)=[Т(С1),...,Т(С5)] • рс =0(Р). рс,
где параметр с е N0 находится из условия
рс_,< к < рс,
т. е. с=]1о§рк [ - целая часть числа 1о§рк.
ДОКАЗАТЕЛЬСТВО. Пусть Н(х) = 0 , ( х ) к' К С 8(х)к‘. Тогда по тео
реме 13 Н(х) - регулярный многочлен и по следствию 2 утверждения 12 А(Р) = А(х') =
1, Т(Р)=Т (Н). Пусть 0(х)=0,(х)-... <35(х). Тогда очевидно, что 0(Р)=0(С)= [О (СО |
О |
(05) ] и по утверждению 14 и следствию 2 утверждения 12 [О (СО,..., 0(08) ] = [Т |
|
(СО,..., Т(С5) ] =Т(0). Теперь остается доказать равенство Т(Н)=Т(С) рс. |
|
Так как С(х) | хт(С)-е, то в силу к=тах{к!,к5} получаем Н(х) [(хТ(С)-е)к и |
в |
силу условия рс'1<к<рс имеем Н(х)|(хт(0) —е)р . Отсюда, пользуясь равенством
(хТ(С) —е)р = х Т(с) р —е , получаем Т(Н) | Т(С) • рс. Более того, так как Т(О) | Т(Н) (поскольку 0(х)|Н(х)), то
Т(Н) = Т(С) р(1, где й < с. Заметим теперь, что (Т(О), р)= 1, поскольку по
утверждению 14 (Т(0*), р)=1 для \ е 1,8 . Следовательно, многочлен хТ(С)-е над Р
взаимно прост со своей производной и потому не имеет кратных множителей в канони ческом разложении над Р.
Поэтому каждый неприводимый делитель многочлена хТ(Н)-е = (х1*0*—о / име ет в его каноническом разложении кратность рй, и так как Н(х) I хТ(Н)-е, то ввиду к=тах{к!к5} имеем к < и ввиду рс-1< к < р° получаем й>с.
Следовательно, й=с, т. е. Т (Н)=Т (С) • рс.
Пример 12. Пусть Р=ОР (рп) и а - элемент из Р* порядка 1. Вычислим период и длину подхода биномиальной последовательности а1*1. По утверждению 6 ее минима