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

UptoLike

ВУЗ: 

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

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

Рубрика: 

67
для натурального числа
n>1 имеет место формула
∏
=
m
m
xQxnqI )();,(
,(2)
где
)(xQ
m
-m - круговой многочлен над
q
F и произведение П
берется по всем натуральным делителям
m числа
1−
n
q
, для ко-
торых
n является показателем, которому принадлежит число q
по модулю
m. (т.е. n -это наименьшее натуральное число, для
которого
)(mod1 mq
n
≡
)
Пример:
Найдем все нормированные неприводимые мно-
гочлены степени
n=4 из кольца
][
2
xF
. Из равенства (2) следует
)()();4,2(
155
xQxQxI
⋅
=
т.к. натуральными делителями m числа
2
4
-1=15, для которых n является показателем, которому принад-
лежит число
q по модулю m т.е.
)(mod1 mq
n
≡
являются m=5 и
m=15 .
(Наименьшее натуральное число
k такое, что
)(mod1 nb
n
≡
называется показателем, которому принадлежит число
b по мо-
дулю
n).
Натуральные делители числа
2
4
-1=15 это m=1,3,5,15. Для
M=3 число n=4 не является показателем, которому принадлежит
q=2 по модулю m=3, т.к. n=4 это не наименьшее натуральное
число для которого,
)(mod1 mq
n
≡
т.е.
)3(mod12 ≡
n
. Очевидно,
при
n=2 имеем
)3(mod12
2
≡
, поэтому делитель M=3 исключа-
ется из рассмотрения.
(если
m=1, то n=4 также не является показателем, которо-
му
m число 2 по модулю 1 при n=1 это показатель).
Определим теперь
Q
5
(x) и Q
15
(x) из выражения (1):
1
1
1
)1()1()1()(
234
5
5/
)5()1(5)(/5
5
+++=
−
−
=−−=−=
∏
xxx
x
x
xxxxQ
d
dd
μμμ
т.к.
μ
(1)=1
μ
(5)= -1 и этот многочлен не приводим в F
2
[x],
что следует из таблиц неприводимых многочленов.
68
15/ ()15(1)5(3)3(5) (15)
15
/15
15
15 5 1 3 1
53
87543
( ) ( 1) ( 1) ( 1) ( 1) ( 1)
(1)(1)
( 1)( 1) ( 1) ( 1)
(1)(1)
1
dd
d
Qx x x x x x
xx
xx x x
xx
x
xxxxx
μμμμμ
−−
=
−=− − − − =
−−
=− − − −= =
−−
=++++++
∏
Q
15
(x) разлагается в произведение двух неприводимых
многочленов из
F
2
[x] степени 4.
)1)(1(1)(
43434578
15
++++=++++++= xxxxxxxxxxxQ
Таким образом, неприводимыми многочленами степени
4
из
F
2
[x] являются три найденных многочлена, и только они.
Перейдем теперь к рассмотрению другого важного вопро-
са, касающегося многочленов над конечными полями, а именно,
к разложению многочленов над заданным полем в виде произве-
дения неприводимых многочленов.
Любой непостоянный многочлен над заданным полем
можно разложить на произведение неприводимых многочленов.
Если конечное поле малого
размера. То имеется много эффек-
тивных алгоритмов для решения этой задачи. Для полей боль-
ших размеров также существуют соответствующие алгоритмы.
Наличие таких алгоритмов особенно важно для решения при-
кладных проблем теории кодирования и криптографии. Чтобы
понять специфику и оценить сложность данной задачи рассмот-
рим некоторые из указанных алгоритмов и лежащие в
их основе
теоретические результаты из теории конечных полей.
Для любого многочлена
][)( xFxf
q
∈
положительной сте-
пени существует каноническое разложение в кольце
][xF
q
. При
построении алгоритмов такого разложения достаточно ограни-
читься рассмотрением только нормированных многочленов. Та-
ким образом, нашей целью является представление нормирован-
ного многочлена
][)( xFxf
q
∈
положительной степени в виде
произведения
)(...)()(
1
1
xfxfxf
k
e
k
e
⋅⋅=
,
где
)()...(
1
xfxf
k
- различные нормированные неприводимые де-

Страницы