Галуев Г.А. Математические основы криптологии

Подождите немного. Документ загружается.

Определение. Пусть f(x)

∈

[x] ненулевой многочлен. Если

f(0)

≠

0, то наименьшее натуральное число е, для которого много-

член

f(x) делит (x

-1) называется порядком многочлена f(x) и

обозначается

ord(f(x)). Если же f(0)=0, то многочлен f(x) одно-

значно представим в виде

f(x)=x

g(x) где h

∈

N, g(x)

∈

[x] и

g(0)=0 и тогда ord(f(x)) многочлена f(x) определяется как

ord(g(x)).

Порядок многочлена иногда называют его

периодом или

экспонентой многочлена. Порядок неприводимого многочлена

можно определить, пользуясь следующей теоремой.

Теорема. Пусть f(x)

∈

[x] неприводимый многочлен сте-

пени

m, удовлетворяющий условию f(0)

≠

0. Порядок этого мно-

гочлена совпадает с порядком любого корня этого многочлена в

мультипликативной группе

F* поля F

Отсюда вытекает важное следствие: Если

f(x)

∈

[x] не-

приводимый многочлен степени

m над полем F

, то его порядок

ord(f(x)) делит число q

-1.

Значения порядков многочленов играют важную роль при

формировании линейных рекуррентных псевдослучайных по-

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

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

тосистем.

Так как каждый многочлен положительной степени можно

записать в виде произведения неприводимых многочленов (ка-

ноническая форма представления многочленов), то вычисление

порядков

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

находить порядок неприводимого многочлена и произведения

попарно взаимно простых многочленов. Ответ на этот вопрос

дают следующие теоремы.

Лемма. Пусть с – натуральное число. Многочлен

f(x)

∈

[x], удовлетворяющий условию f(0)

≠

0 делит двучлен x

1 тогда и только тогда, когда ord(f(x)) делит число с.

Следствие. Если е

и е

натуральные числа, то НОД мно-

гочленов (

-1) и (x

-1) в F

[x] равен (x

-1), где d=НОД(е

, е

Теорема. Пусть n

∈

N и g(x) – неприводимый многочлен

над конечным полем характеристики

P, такой что g(0)

≠

0. Тогда

для многочлена вида

f(x)=g

(x) имеем

ord(f(x))=ord(g

(x))=p

ord(g(x)),

где

t – наименьшее целое число, для которого p

≥

Теорема. Пусть g

(x),...,g

(x) – попарно взаимно простые

ненулевые многочлены над полем

, и пусть

f(x)=g

(x)

⋅

(x)...g

(x), тогда

ord(f(x))=ord(g

(x))

⋅

ord(g

(x))=НОК(ord(g

(x),...,ord(g

Иными словами, порядок произведения попарно взаимно про-

стых ненулевых многочленов равен наименьшему общему крат-

ному порядков его сомножителей (многочленов).

Пример:

f(x)=x

∈

[x].

Каноническое разложение

f(x) над полем F

имеет вид

f(x)=(x

+x+1)

+x+1). Т.к. ord(x

+x+1)=3 и имея

ord(g

(x)=p

ord(g(x)), получаем, что ord((x

+x+1)

)=2

⋅

3=12 т.к. у

нас

т.е. p=2 и t=2 чтобы 2

>3). Далее ord(x

+x+1)=15. Тогда

ord(f(x))=НОК(12,15)=60.

Обобщить эти результаты можно теоремой.

Теорема. Пусть F

конечное поле характеристики p. Если

ffaf ⋅⋅⋅= ...

каноническое разложение в кольце F

[x] мно-

гочлена

f(x)

∈

[x] положительной степени, такого что f(0)

≠

0, то

))(,...),(()...())((

1 K

tnK

fordfordНОКpfafordxford =⋅⋅=

где

t – наименьшее целое число, удовлетворяющее нера-

венству

≥

max{n

,...,n

Из определения порядка

е многочлена f(x) следует, что е

это наименьшее натуральное число, удовлетворяющее сравне-

нию:

≡

1(mod(f(x)),

т.к. это сравнение означает, что

f(x) делит x

-1. Отсюда следует

еще один способ определения порядка многочленов. Согласно

приведенному выше следствию 1 порядок е делит число

-1,

где

m степень многочлена f(x). Предполагая q

>2 будем исхо-

дить из разложения числа

-1 на простые сомножители:

∏

=−

Для каждого Sj

≤

1 найдем вычеты одночлена

/)1( −

по модулю

f(x) (т.е. остатки от их деления на f(x)). Обычно это

делается перемножением подходящим образом выбранного на-

бора вычетов по модулю f(x) степеней

,...,,,

−m

gqq

xxxx

пере-

менной

x. При этом, если

))(mod(1

/)1(

xfx

≠

−

,то число е де-

лится на

p , в противном случае, число е не делится на

p . В

последнем случае мы выясняем, будет ли число е делится на

1−

p ,

2−

p , ...,

p , вычисляя соответственно вычеты по модулю

f(x) следующих степеней переменной x:

/)1(

−

/)1(

−

,...,

/)1( −

. Такой подсчет проводится для каждого

простого делителя

числа q

-1 и в итоге находится порядок

e=ord(f(x)).

В этом методе ключевым моментом является разложение

на простые сомножители натурального числа

-1. Существуют

обширные таблицы для полного такого разложения указанных

чисел, особенно для

q=2 т.е. для полей F

и F

7. Элементы теории конечного поля.

Многочлены над конечными полями.

Определение. Многочлен

][)( xFxf

∈

степени

1≥m

на-

зывается примитивным многочленом над полем

F , если он яв-

ляется минимальным многочленом над

F некоторого прими-

тивного элемента расширения

поля

F .

Это определение опирается на приведенные, на прошлой

лекции понятия примитивного элемента и означает, что прими-

тивный многочлен над

F степени m - это нормированный мно-

гочлен который неприводим над

F и имеет корень

Fa ∈

который является образующим мультипликативной группы

поля

F .

Теорема. Многочлен

][)( xFxf

∈

степени m является

примитивным тогда и только тогда, когда он нормирован и, та-

кой, что

1q)) ord(f(x 0)0(

−=≠ иf

Рассмотрим теперь вопрос о числе нормированных непри-

водимых многочленов над конечным полем

F .

Теорема. Для каждого конечного поля

F и каждого n

∈Ν

произведение всех нормированных неприводимых многочленов

над

F , степень которых делит n, равно

−

Следствие: Если

)(dN

число нормированных неприво-

димых многочленов из

][xF

степени d, то

∑

ddNq

)(

для

всех

n, где суммирование берется по всем положительным дели-

телем

d числа n.

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

функцию Мебиуса можно получить точную формуле для числа

нормированных неприводимых многочленов фиксированной

степени из кольца

][xF

Для

∈

N функция Мебиуса

(n) удовлетворяет соотноше-

нию

∑

⎩

⎨

⎧

1, 0

1, 1

)(

Тогда существует

теорема: Число

)(nN

нормированных

неприводимых многочленов степени

n в кольце

][xF

равно

];)20()10()5()4()2()1[

)20(

2451020

qqqqqqN

μμμμμμ

+++++=

Для функции Мебиуса справедливо выражение

⎪

⎩

⎪

⎨

⎧

−

числа простого некоторого квадрат на делится d если 0,

чиселстых ие k пропроизведен d , )1(

1, 1

)( если

Тогда

).(

)20(N

0)20( 1)10( 1)5(

0)4( 1)2( 1)1(

241020

qqqq +−−=

==−=

−=

μμμ

(1) 1

(2) 1 . . 2 2 4

(4) 0 . . 4 2 4

(5) 1 . . 5 , k 1 (-1) 1

(10) 1

ï î î ï ðåäåëåí èþ

ò ê äåëèò ñÿ í à êâàäðàò ï ðî ñò î ãî ÷èñëà

ò ê ïðîñòîå÷èñëî

=− =

=− = → =−

.. 1 0 2 5 (ï ðî èçâåäåí èå äâóõ ï ðî ñòûõ ÷èñåë),

k2 (-1) 1

òê =⋅

=→ =

Перейдем к рассмотрению вопросов построения неприво-

димых многочленов.

Ранее мы определили число нормированных многочленов

данной степени

n в кольце

][xF

. Получим теперь формулу для

произведения всех нормированных неприводимых многочленов

данной степени

n из кольца

][xF

Теорема (*). Пусть

),,(

произведение всех нормиро-

ванных неприводимых многочленов степени

n из кольца

][xF

Тогда оно определяется формулой

∏

−=

xxxnqI

)(

)(),,(

Пример

: q=2, n=4. Здесь d=1,2,4.

16 (1)4 (2)2 (4)

16 15

16 14 12 0

12 9 6 3

(2,4;)( )()()

( )()()

I x x x xx xx

xxx

x x xx xx

xxx

xxxx

μμ μ

−

−⋅−⋅− =

−−

−⋅− ⋅− = = =

−−

=++++

0)4(, 1)2(, 1)1(

−

15 3

15 12 12 9 6 3

12 9

1 | 1

xxxxxx

−−

−

++++

−

Все нормированные неприводимые многочлены степени

из

][xF

можно найти, различая на множители многочлен

);,(

. В этой связи было бы полезно представить

);,(

частично разложенном виде. Этого можно добиться, опираясь на

следующие факты.

Теорема. Для поля F характеристики p и натурального

числа

n, не делящегося на р, n - круговой многочлен

)(xQ

над

F задается выражением:

∏

−=

ddn

xxQ

)(/

)1()(

(1)

Отсюда имеет место теорема.

Теорема. Пусть

);,(

тоже, что и в теореме (*). Тогда

для натурального числа

n>1 имеет место формула

∏

xQxnqI )();,(

,(2)

где

)(xQ

-m - круговой многочлен над

F и произведение П

берется по всем натуральным делителям

m числа

1−

, для ко-

торых

n является показателем, которому принадлежит число q

по модулю

m. (т.е. n -это наименьшее натуральное число, для

которого

)(mod1 mq

≡

)

Пример:

Найдем все нормированные неприводимые мно-

гочлены степени

n=4 из кольца

][

. Из равенства (2) следует

)()();4,2(

155

xQxQxI

⋅

т.к. натуральными делителями m числа

-1=15, для которых n является показателем, которому принад-

лежит число

q по модулю m т.е.

)(mod1 mq

≡

являются m=5 и

m=15 .

(Наименьшее натуральное число

k такое, что

)(mod1 nb

≡

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

b по мо-

дулю

n).

Натуральные делители числа

-1=15 это m=1,3,5,15. Для

M=3 число n=4 не является показателем, которому принадлежит

q=2 по модулю m=3, т.к. n=4 это не наименьшее натуральное

число для которого,

)(mod1 mq

≡

т.е.

)3(mod12 ≡

. Очевидно,

при

n=2 имеем

)3(mod12

≡

, поэтому делитель M=3 исключа-

ется из рассмотрения.

(если

m=1, то n=4 также не является показателем, которо-

му

m число 2 по модулю 1 при n=1 это показатель).

Определим теперь

(x) и Q

(x) из выражения (1):

)1()1()1()(

234

)5()1(5)(/5

+++=

−

=−−=−=

∏

xxx

xxxxQ

μμμ

т.к.

(1)=1

(5)= -1 и этот многочлен не приводим в F

[x],

что следует из таблиц неприводимых многочленов.

15/ ()15(1)5(3)3(5) (15)

/15

15 5 1 3 1

87543

( ) ( 1) ( 1) ( 1) ( 1) ( 1)

(1)(1)

( 1)( 1) ( 1) ( 1)

(1)(1)

Qx x x x x x

xx x x

xxxxx

μμμμμ

−−

−=− − − − =

−−

=− − − −= =

−−

=++++++

∏

(x) разлагается в произведение двух неприводимых

многочленов из

[x] степени 4.

)1)(1(1)(

43434578

++++=++++++= xxxxxxxxxxxQ

Таким образом, неприводимыми многочленами степени

из

[x] являются три найденных многочлена, и только они.

Перейдем теперь к рассмотрению другого важного вопро-

са, касающегося многочленов над конечными полями, а именно,

к разложению многочленов над заданным полем в виде произве-

дения неприводимых многочленов.

Любой непостоянный многочлен над заданным полем

можно разложить на произведение неприводимых многочленов.

Если конечное поле малого

размера. То имеется много эффек-

тивных алгоритмов для решения этой задачи. Для полей боль-

ших размеров также существуют соответствующие алгоритмы.

Наличие таких алгоритмов особенно важно для решения при-

кладных проблем теории кодирования и криптографии. Чтобы

понять специфику и оценить сложность данной задачи рассмот-

рим некоторые из указанных алгоритмов и лежащие в

их основе

теоретические результаты из теории конечных полей.

Для любого многочлена

][)( xFxf

∈

положительной сте-

пени существует каноническое разложение в кольце

][xF

. При

построении алгоритмов такого разложения достаточно ограни-

читься рассмотрением только нормированных многочленов. Та-

ким образом, нашей целью является представление нормирован-

ного многочлена

][)( xFxf

∈

положительной степени в виде

произведения

)(...)()(

xfxfxf

⋅⋅=

где

)()...(

xfxf

- различные нормированные неприводимые де-

лители многочлена

)(

в кольце

][xF

;

ee ,...,

- натуральные числа.

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

проблему можно свести к проблеме разложения многочлена без

кратных неприводимых сомножителей, т.е. когда все

1...

===

Для этого, применяя алгоритм Евклида, найдем многочлен,

(x))'),(()(

НОД

d =

т.е. наибольший общий делитель

)(

и его производной

)('

Если

d(x)=1, то известно, что

)(

не имеет кратных со-

множителей (существует соответствующая теорема, доказы-

вающая этот факт).

Если

)()(

, то очевидно (т.к.

)()('

)

0)('

, а это значит, что

xgxf )()( =

для неко-

торого многочлена

][)( xFxg

∈

, где р - характеристика поля

][xF

. Указанную процедуру редукции можно при необходимо-

сти повторить и для

g(x) пока не получим представление

xhxf )()( =

, где

0)('

≠

Если

d(x) отличен от 1 и от )(

он является нетривиаль-

ным делителем

)(

и тогда многочлен

)(

не имеет кратных

неприводимых сомножителей. Мы придем к разложению

)(

разложив по отдельности многочлены меньшей степени

d(x) и

)(

. Если d(x) все еще имеет кратные сомножители, для него

повторяем указанный процесс редукции.

Таким образом, применяя описанную процедуру, нужное

число раз, мы сведем исходную задачу к задаче разложения не-

которого числа многочленов, не имеющих кратных неприводи-

мых сомножителей. Канонические разложения этих многочле-

нов сразу приведут к каноническому разложению исходного

многочлена

)(

. Это позволяет в дальнейшем рассматривать

только многочлены, не имеющие кратных неприводимых со-

множителей. В этом смысле следующая теорема является основ-

ной.

Теорема. Если

][)( xFxf

∈

нормированный многочлен

положительной степени и многочлен

][)( xFxh

∈

удовлетворяет

условию

(mod ( )), ( ) ( ( ), ( ) )

xòî

x ÍÎÄ

xhx c

∈

≡

=−

∏

Представление в теореме выражения, вообще говоря, еще

не дает полного разложения многочлена

)(

, т.к. многочлен

))(),(( c

ОД

−

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

][xF

. Поэтому если h(x) таков, что указанная теорема приводит

к некоторому нетривиальному разложению (но не полному)

многочлена

)(

, он называется

- разлагающим многочле-

ном. Любой многочлен

)(

, обладающий свойством

))((mod xfhh

≡

, очевидно, является

- разлагающим. По-

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

разложения

)(

мы должны найти способы построения

разлагающих многочленов. Иными словами, задача разложения

усложняется. Более того, даже если найдем способ построе-

ния

разлагающих многочленов из выражения для

)(

в тео-

реме видно, что для разложения

)(

требуется вычисление q

НОД, что при больших размерах полей (т.е.

q) уже представляет

собой вычислительную процедуру.

Тем не менее, рассмотрим один из способов построения

- разлагающих многочленов. Этот способ получил название ал-

горитма Берлекэмпа. В его основе лежит так называемая

китай-

ская теорема об остатках для многочленов: Пусть

F поле, и

)(),...,(

xgxg

произвольные, а

)(),...,(

xfxf

ненулевые по-

парно взаимно простые многочлены из

][xF

. Тогда система

сравнений вида

kixfxgxh

,...,1)) ()(mod()(

≡

имеет един-

ственное решение

][)( xFxh

∈

по модулю

)(),...,()(

xfxfxf

Допустим теперь, что

)(

не имеет кратных сомножите-

лей, так что

)(),...,()(

xfxfxf

произведение различных

нормированных неприводимых многочленов над полем

F . То-

гда для любого

k -го набора

)(),...,(

xcxc

элементов поля

F ,

согласно китайской теореме, существует единственный много-

член

][)( xFxh

∈

, такой что выполняется

(x))deg()) deg(h(x 1)), ((mod)( fиkixfcxh

≤≤≡

Этот многочлен удовлетворяет условию

kixfxhccxh

,...,1)) ()(mod()( =≡≡≡

И поэтому справедливо сравнение:

() ()(mod ()) deg(()) deg( ())

h x hx fx hx fx=<

С другой стороны, если многочлен

)(

h является решени-

ем сравнения, то из равенства

∏

∈

−=−

cxhxhxh ))(()()(

, в силу

взаимной попарной простоты сомножителей правой части, сле-

дует, что каждый неприводимый делитель многочлена

)(

должен делить один и только один из многочленов

))(( c

−

Таким образом каждое решение

)(

h сравнения (1) удовлетво-

ряет системе сравнений

kixfcxh

,...,1)) ((mod)(

≡

для не-

которого

k -го набора

)(),...,(

xcxc

элементов поля

. Следо-

вательно, данное сравнение имеет ровно

решений.

Чтобы найти эти решения сведем рассматриваемое сравне-

ние к системе линейных уравнений. Полагая

))(deg(

вы-

числяя

по модулю )(

посмотрим nn

матрицу

),(

bbB =

1,0

−

≤

≤ nji

1,..,1 )))((mod(

−==

∑

−

nixfxbx

Тогда многочлен

][...)(

110

xFxaxaaxh

∈+++=

−

будет решением рассматриваемого сравнения тогда и только то-

гда, когда (

110

,..,,

−n

aaa

) является решением системы линейных

уравнений, которая в матричной форме имеет вид

),...,,(),..,,(

110110 −−

aaaBaaa

. Эту систему можно также запи-

сать в виде

)0,...,0,0())(,..,,(

110

−

IBaaa

, где I единичная

матрица

на

F . Согласно доказанному выше, система

уравнений имеет

q решений. Это значит, что размерность про-

странства решений этой системы равна

K т.е. числу различных

нормированных неприводимых делителей многочлена

)(

, а

ранг матрицы

B -I равен r=n -k. Определяя ранг (здесь не будем

описывать алгоритмы поиска ранга матриц т.к. их можно найти

в известной литературе)

r=n -k мы тем самым находим число K

различных нормированных неприводимых делителей

)(

тем самым можем узнать до каких пор необходимо продолжать

процедуру разложения. Вычислив ранг

u матрицы B -I находим

число

k=n -r. Если 1

, значит )(

неприводим над

F и

процедура разложения заканчивается. Если

2≥

, то берем

разлагающий базисный многочлен

)(

и находим

))(),((

cxhxfНОД

−

для всех

∈

. В результате поучим не-

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

)(

. Если использование

)(

xh не привело к разложению )(

на K сомножителей, то

переходим к следующему

- разлагающему многочлену )(

и находим

))(),((

cxhxgНОД

−

для всех

∈

и всех нетри-

виальных делителей

g(x) многочлена )(

, полученных на пре-

дыдущем этапе. Так продолжается до тех пор, пока не получим

все

K неприводимых сомножителей )(

. Существует доказа-

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

нахождению всех

K сомножителей )(

Таким образом, в данном алгоритме задача вычисления

- разлагающих многочленов сводится к решению систем линей-

ных уравнений, путем их представления в матричной форме за-

писи.

Из представленного алгоритма видно, насколько трудоем-

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

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

приводимых многочленов. Этот факт и нашел широкое приме-

нение таких трудоемких задач при

построении различных крип-

тографических систем. С понятием многочленов и процедурами

их деления друг а друга тесно связаны вопросы формирования

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

полями, которые находят широкое применение при создании по-

точных криптосистем. Поэтому рассмотрим вопросы формиро-

вания линейных рекуррентных последовательностей над конеч-

ными полями.

8. Элементы теории конечного поля. Линейные

рекуррентные последовательности над конечными

полями.

Результаты, полученные в теории линейных рекуррентных

последовательностей над конечными полями, находят в настоя-

щее время практическое применение для генерации последова-

тельностей псевдослучайных чисел с гарантированно хорошими

для криптографии свойствами и служат основой для построения

современных поточных криптосистем. Поэтому рассмотрим

принципы построения линейных рекуррентных последователь-

ностей и важнейшие теоретические результаты, связанные с

ни-

ми и полученные в рамках теории конечных полей.

Определение. Пусть к - натуральное число,

110

,...,,,

−k

aaaa

- заданные элементы конечного поля

F . По-

следовательность

,...,

ss элементов поля

F , удовлетворяю-

щая соотноше-

нию

aSaSaSaS

nknkknkkn

−+−−+−+ 02211

...

,...2,1=n называется линейной рекуррентной последователь-

ностью (ЛРП) K - го порядка над полем

F .

Первые члены

110

,...,,

−k

SSS

однозначно определяют всю

последовательность и называются

начальными значениями.

Такое соотношение еще называют

линейным рекуррентным

соотношением K - го порядка. Будем считать, что линейное ре-

куррентное соотношение

K - го порядка (К - го порядка над по-

лем

F ) называется однородным, если q=0, в противном случае

неоднородным.

Пример.

Пусть порядок К=4, тогда имеем линейную ре-

куррентную последовательность

4 порядка над полем

вида:

aSaSaSaSaS

nnnnn

++++ 01122334

В практическом плане линейные рекуррентные последова-

тельности реализуются на базе современных компьютерных сис-

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

данные в ЭВМ представляются с помощью элементов двух ти-

пов

0 и 1. Т.е. вся обработка информации осуществляется на ос-

нове элементов простого конечного поля

F или его расшире-

ний

. Реализация линейных рекуррентных последовательно-

стей над полем

F может быть достаточно просто осуществлена

на основе регистров сдвига с обратной связью. Пусть у нас име-

ется однородное линейное рекуррентное соотношение вида (т.е.

порядка

К=4):

nnnnn

SaSaSaSaS

01122334

++++

3210

=== aaaa

. Тогда его реализация на основе регистра

сдвига из

К=4 разрядов с обратной связью будет иметь вид:

Если какой либо из коэффициентов

321

,, aaa

равен нулю,

то соответствующий сумматор

⊕ из цепи обратной связи ис-

ключается.

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

моменты времени

,...2,1

на выходе регистра происходит гене-

рация последовательности

,...,,

21 ++ nnn

SSS

Вектор

},...,,{

11 −++ knnn

SSS

- это вектор n - го состояния регистра. При

n=0 вектор

},...,,{

110 −k

SSS

- это вектор начального состояния.

Характерной особенностью линейных рекуррентных по-

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

ность в смысле следующего определения.

Определение. Пусть S - произвольное непустое множество,

и пусть

,...,

последовательность элементов из множества S.

Если существуют целые числа

0 n 0

>> иr

, такие что,

nrn

SS =

для всех

nn ≥

, то последовательность

,...,

на-

зывается

периодической последовательностью, а r - периодом

этой последовательности.

Наименьший из всех возможных периодов называется

ми-

нимальным периодом.

Лемма. Каждый период периодической последовательно-

сти делится на ее минимальный период.

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

,...,

с минимальным периодом

r называется чисто периодической,

если равенство

nrn

выполняется при всех

,...2,1,0

Рассмотрим теперь основные результаты о свойствах пе-

риодичности линейных рекуррентных последовательностей над

конечными полями, т.к. для криптографических приложений

желательно иметь ЛПР с

max r .

Теорема. Пусть

- произвольное конечное поле, К - не-

которое натуральное число. Тогда каждая линейная рекуррент-

ная последовательность

К - го порядка над полем

F является

периодической. При этом ее минимальный период

r удовлетво-

ряет неравенству

qr ≤

, а в случае однородной последователь-

ности

1−≤

Достаточным (но не необходимым) условием чистой пе-

риодичности ЛРП является следующее:

Теорема. Пусть

,...,

- ЛРП над конечным полем, оп-

ределяемая рекуррентным соотношением. Если коэффициент

равен

0 т.е.

, то последовательность

,...,

является

чисто периодической.

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

тельностей над полем

F удовлетворяющих соотношению К -

го порядка, т.е

nknkknkkn

SaSaSaS

02211

...

−+−−+−+

можно выделить одну ЛРП с максимальным значением

минимального периода

r, которую называют импульсной функ-

цией или ЛРП, порожденной импульсом. Эта последователь-

ность обозначается

,...,

и определяется начальными значе-

ниями

1,0...

1210

−− kk

dddd

(

1k ,1

приd

) и ли-

нейным рекуррентным соотношением

nknkknkkn

dadadad

02211

...

−+−−+−+

, (n=0,1,…)

Пример:

Пусть есть линейное рекуррентное соотношение

nnn

SSS +=

++ 15

, (n=0,1,…) над полем

F .

Устройство для ее реализации имеет вид:

Импульсная функция

,...,

, соответствующая этому ре-

куррентному соотношению получается при начальном заполне-

ния регистра кодом

1 0 0 0 0

4321

++++ nnnnn

SSSSS

Тогда на выходе регистра получим ЛРП, порожденную

импульсом

с минимальным периодом

r=21.

Линейные рекуррентные последовательности над конеч-

ными полями тесно связаны с рассмотренными нами ранее мно-

гочленами.

Пусть

,...,

однородная ЛРП К - го порядка над полем

F , удовлетворяющая рекуррентному соотношению:

nknkknkkn

SaSaSaS

02211

−+−−+−+

, (n=0,1,…) где

−

≤

≤∈ kjFa

. Многочлен вида

][...)(

xFaxaxaxxf

∈−−−=

−

называется харак-

теристическим многочленом данной ЛРП. Его вид зависит толь-

ко от вида линейного рекуррентного соотношения.

Пример:

Пусть ЛРП над полем

определяется соотноше-

нием

,...1,0

nSSS

nnn

. Тогда соответствующий ей ха-

рактеристический многочлен имеет вид

1)(

−−= xxxf

Существует прямая связь между периодом ЛРП и поряд-

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

Теорема. Пусть

,...,

- однозначная на ЛРП над полем

F и

][)( xFxf

∈

- характеристический многочлен этой по-

следовательности. Тогда линейный период этой последователь-

ности делит

))((

ord

, а минимальный период соответствую-

щей импульсной функции равен

))((

ord

Теорема. Пусть

,...,

- однородная ЛРП над полем

F с

ненулевых вектором начального состояния. Пусть ее характери-

стический многочлен

][)( xFxf

∈

является неприводимым над

полем

F и удовлетворяет условию

0)0(

≠

. Тогда ЛРП

,...,

является чисто периодической последовательностью и

ее минимальный период

))((

ord

Для практических приложений требуется формирование

ЛРП с как можно большим минимальным периодом. Каким об-

разом получить такую ЛРП отвечают следующие факты из тео-

рии конечного поля (мы уже знаем, что

max значение мини-

мального периода не превышает

1−

Определение. Однородная линейная рекуррентная после-

довательность над полем

F , характеристический многочлен

который является примитивным над этим полем

F , а вектор

начального состояния - ненулевым вектором, называется

после-

довательностью максимального периода над полем

F .

Это подтверждает следующая теорема.

Теорема. Каждая последовательность К - го порядка и мак-

симального периода над полем

F является чисто периодиче-

ской последовательностью, а её максимальный период равняется

1−

, наибольшему из возможных значений, которое может

принимать минимальный период однородной ЛРП

К - го поряд-

ка над полем

F .

Пример:

Пусть есть рекуррентное соотношение для одно-

родной ЛРП над

F вида:

,...1,0

2347

++++

nSSSSS

nnnnn

Характеристический многочлен этой ЛРП имеет вид:

][1)(

2347

xFxxxxxf ∈−−−−=

и является примитивным над

F т.е. является нормированным неприводимым над

F много-

членом порядка

12712))((

=−=xford

Соответствующий регистр сдвига для заданного рекур-

рентного соотношения будет иметь вид:

n=0,1,…

Если в качестве вектора начального состояния регистра

взять ненулевой элемент, то, согласно теореме, на его выходе

получим последовательность

,...,

с минимальным перио-

дом 127, т.е. все возможные

− ненулевые векторы встре-

чаются в качестве векторов состояний этой последовательности.

При разных начальных ненулевых векторах регистра получим

разные ЛРП с одним и тем же периодом 127, но с некоторым

сдвигом относительно друг друга.

Вектор начального состояния регистра сдвига также можно

представить в виде многочлена

g(x) степени <К. Тогда, по сути

дела, формирование ЛРП обусловлено процедурой деления мно-

гочленов

)(

. Следует отметить, что из представленных выше

результатов становится понятно, почему криптографы всего ми-

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

степени

К (т.к.

−

). Но это NP полная задача и ее реше-

ние требует очень больших затрат. В связи с этим в теории ко-

нечного поля решены вопросы о том, можно ли осуществить

операции почленного сложения или умножения линейных ре-

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

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

ЛРП.

Пусть

- линейная рекуррентная последовательность вида

,...,

, а

- линейная рекуррентная последовательность вида

,...,

над полем

F . Тогда произведением этих последова-

тельностей будки считать последовательность

⋅

вида

,...,

1100

tStS

. Аналогично определяется произведение любого числа

ЛРП. При таком определении операции произведения ЛРП в

теории конечного поля получен ряд важных результатов:

1. Произведение любого конечного числа линейных рекур-

рентных последовательностей над полем

само является ли-

нейной рекуррентной последовательностью над

F .

Теорема. Пусть

),...,2,1( hi

- ЛРП над полем

F . И

пусть их минимальные периоды равны соответственно

),...,2,1( hi =

. Тогда если числа

rr ,...,

попарно взаимно

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

,...,,

равен произведению

rr ,...,

Аналогично вводится операция суммирования ЛРП. При

этом интересно отметить, что последний результат аналогичен и

для операции сложения ЛРП:

Теорема. Пусть

ЛРП над полем

),...,2,1( hi

на

- их минимальные периоды. Тогда если числа

попарно вза-

имно простые, то минимальный период суммарной последова-

тельности

...

равен произведению

rrr ...

⋅

Таким образом, суммирование и умножение ЛРП позволя-

ет увеличить их минимальный период. (В этом вопросе есть оп-

ределенные тонкости математического характера, но о них мож-

но узнать в соответствующей литературе).

Для практических приложений весьма важным является