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

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

69
лители многочлена
)(
x
f
в кольце
][xF
q
;
k
ee ,...,
1
- натуральные числа.
Прежде всего, упростим задачу, показав, что указанную
проблему можно свести к проблеме разложения многочлена без
кратных неприводимых сомножителей, т.е. когда все
1...
1
===
k
ee
.
Для этого, применяя алгоритм Евклида, найдем многочлен,
(x))'),(()(
f
x
f
НОД
x
d =
т.е. наибольший общий делитель
)(
x
f
и его производной
)('
x
f
.
Если
d(x)=1, то известно, что
)(
f
не имеет кратных со-
множителей (существует соответствующая теорема, доказы-
вающая этот факт).
Если
)()(
x
f
x
d
=
, то очевидно (т.к.
)()('
x
f
x
f
<
)
0)('
=
x
f
, а это значит, что
p
xgxf )()( =
для неко-
торого многочлена
][)( xFxg
q
∈
, где р - характеристика поля
][xF
q
. Указанную процедуру редукции можно при необходимо-
сти повторить и для
g(x) пока не получим представление
s
p
xhxf )()( =
, где
0)('
≠
x
h
.
Если
d(x) отличен от 1 и от )(
x
f
он является нетривиаль-
ным делителем
)(
x
f
и тогда многочлен
)(
)(
xd
xf
не имеет кратных
неприводимых сомножителей. Мы придем к разложению
)(
x
f
,
разложив по отдельности многочлены меньшей степени
d(x) и
)(
)(
xd
xf
. Если d(x) все еще имеет кратные сомножители, для него
повторяем указанный процесс редукции.
Таким образом, применяя описанную процедуру, нужное
число раз, мы сведем исходную задачу к задаче разложения не-
которого числа многочленов, не имеющих кратных неприводи-
мых сомножителей. Канонические разложения этих многочле-
нов сразу приведут к каноническому разложению исходного
70
многочлена
)(
f
. Это позволяет в дальнейшем рассматривать
только многочлены, не имеющие кратных неприводимых со-
множителей. В этом смысле следующая теорема является основ-
ной.
Теорема. Если
][)( xFxf
q
∈
нормированный многочлен
положительной степени и многочлен
][)( xFxh
q
∈
удовлетворяет
условию
(mod ( )), ( ) ( ( ), ( ) )
q
q
cF
hh
f
xòî
f
x ÍÎÄ
f
xhx c
∈
≡
=−
∏
Представление в теореме выражения, вообще говоря, еще
не дает полного разложения многочлена
)(
x
f
, т.к. многочлен
))(),(( c
x
h
x
f
Н
ОД
−
может оказаться приводимым в кольце
][xF
q
. Поэтому если h(x) таков, что указанная теорема приводит
к некоторому нетривиальному разложению (но не полному)
многочлена
)(
x
f
, он называется
f
- разлагающим многочле-
ном. Любой многочлен
)(
x
h
, обладающий свойством
))((mod xfhh
q
≡
, очевидно, является
f
- разлагающим. По-
этому , чтобы на основе указанной теоремы добиться полного
разложения
)(
x
f
мы должны найти способы построения
f
-
разлагающих многочленов. Иными словами, задача разложения
f
усложняется. Более того, даже если найдем способ построе-
ния
f
разлагающих многочленов из выражения для
)(
x
f
в тео-
реме видно, что для разложения
)(
x
f
требуется вычисление q
НОД, что при больших размерах полей (т.е.
q) уже представляет
собой вычислительную процедуру.
Тем не менее, рассмотрим один из способов построения
f
- разлагающих многочленов. Этот способ получил название ал-
горитма Берлекэмпа. В его основе лежит так называемая
китай-
ская теорема об остатках для многочленов: Пусть
q
F поле, и
)(),...,(
1
xgxg
k
произвольные, а
)(),...,(
1
xfxf
k
ненулевые по-
парно взаимно простые многочлены из
][xF
q
. Тогда система

Страницы