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

UptoLike

ВУЗ: 

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

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

Рубрика: 

71
сравнений вида
kixfxgxh
ii
,...,1)) ()(mod()(
=
≡
имеет един-
ственное решение
][)( xFxh
q
∈
по модулю
)(),...,()(
1
xfxfxf
k
=
.
Допустим теперь, что
)(
x
f
не имеет кратных сомножите-
лей, так что
)(),...,()(
1
xfxfxf
k
=
произведение различных
нормированных неприводимых многочленов над полем
q
F . То-
гда для любого
k -го набора
)(),...,(
1
xcxc
k
элементов поля
q
F ,
согласно китайской теореме, существует единственный много-
член
][)( xFxh
q
∈
, такой что выполняется
(x))deg()) deg(h(x 1)), ((mod)( fиkixfcxh
ii
<
≤≤≡
.
Этот многочлен удовлетворяет условию
kixfxhccxh
ii
q
i
q
,...,1)) ()(mod()( =≡≡≡
.
И поэтому справедливо сравнение:
() ()(mod ()) deg(()) deg( ())
q
h x hx fx hx fx=<
С другой стороны, если многочлен
)(
x
h является решени-
ем сравнения, то из равенства
∏
∈
−=−
q
Fc
q
cxhxhxh ))(()()(
, в силу
взаимной попарной простоты сомножителей правой части, сле-
дует, что каждый неприводимый делитель многочлена
)(
x
f
должен делить один и только один из многочленов
))(( c
x
h
−
.
Таким образом каждое решение
)(
x
h сравнения (1) удовлетво-
ряет системе сравнений
kixfcxh
ii
,...,1)) ((mod)(
=
≡
для не-
которого
k -го набора
)(),...,(
1
xcxc
k
элементов поля
q
F
. Следо-
вательно, данное сравнение имеет ровно
k
q
решений.
Чтобы найти эти решения сведем рассматриваемое сравне-
ние к системе линейных уравнений. Полагая
n
x
=
))(deg(
вы-
числяя
iq
x
по модулю )(
x
f
посмотрим nn
×
матрицу
),(
ji
bbB =
1,0
−
≤
≤ nji
72
1,..,1 )))((mod(
1
0
−==
∑
−
=
nixfxbx
n
j
j
ij
iq
Тогда многочлен
][...)(
1
110
xFxaxaaxh
q
n
n
∈+++=
−
−
будет решением рассматриваемого сравнения тогда и только то-
гда, когда (
110
,..,,
−n
aaa
) является решением системы линейных
уравнений, которая в матричной форме имеет вид
),...,,(),..,,(
110110 −−
=
nn
aaaBaaa
. Эту систему можно также запи-
сать в виде
)0,...,0,0())(,..,,(
110
=
−
−
IBaaa
n
, где I единичная
матрица
nn
×
на
q
F . Согласно доказанному выше, система
уравнений имеет
k
q решений. Это значит, что размерность про-
странства решений этой системы равна
K т.е. числу различных
нормированных неприводимых делителей многочлена
)(
x
f
, а
ранг матрицы
B -I равен r=n -k. Определяя ранг (здесь не будем
описывать алгоритмы поиска ранга матриц т.к. их можно найти
в известной литературе)
r=n -k мы тем самым находим число K
различных нормированных неприводимых делителей
)(
x
f
и
тем самым можем узнать до каких пор необходимо продолжать
процедуру разложения. Вычислив ранг
u матрицы B -I находим
число
k=n -r. Если 1
=
k
, значит )(
x
f
неприводим над
q
F и
процедура разложения заканчивается. Если
2≥
k
, то берем
f
-
разлагающий базисный многочлен
)(
2
xh
и находим
))(),((
2
cxhxfНОД
−
для всех
q
Fc
∈
. В результате поучим не-
которое нетривиальное разложение
)(
x
f
. Если использование
)(
2
xh не привело к разложению )(
x
f
на K сомножителей, то
переходим к следующему
f
- разлагающему многочлену )(
3
xh
и находим
))(),((
3
cxhxgНОД
−
для всех
q
Fc
∈
и всех нетри-
виальных делителей
g(x) многочлена )(
x
f
, полученных на пре-
дыдущем этапе. Так продолжается до тех пор, пока не получим
все
K неприводимых сомножителей )(
x
f
. Существует доказа-

Страницы