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

UptoLike

ВУЗ: 

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

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

Рубрика: 

65
степени из кольца
][xF
q
.
Для
n
∈
N функция Мебиуса
μ
(n) удовлетворяет соотноше-
нию
∑
⎩
⎨
⎧
>
=
=
nd
n
n
d
/
1, 0
1, 1
)(
μ
.
Тогда существует
теорема: Число
)(nN
q
нормированных
неприводимых многочленов степени
n в кольце
][xF
q
равно
];)20()10()5()4()2()1[
20
1
)20(
2451020
qqqqqqN
q
μμμμμμ
+++++=
Для функции Мебиуса справедливо выражение
⎪
⎩
⎪
⎨
⎧
−
=
=
числа простого некоторого квадрат на делится d если 0,
чиселстых ие k пропроизведен d , )1(
1, 1
)( если
d
d
k
μ
Тогда
).(
20
1
)20(N
0)20( 1)10( 1)5(
0)4( 1)2( 1)1(
241020
q
qqqq +−−=
==−=
=
−=
=
μμμ
μ
μ
μ
2
2
1
(1) 1
(2) 1 . . 2 2 4
(4) 0 . . 4 2 4
(5) 1 . . 5 , k 1 (-1) 1
(10) 1
ï î î ï ðåäåëåí èþ
ò ê äåëèò ñÿ í à êâàäðàò ï ðî ñò î ãî ÷èñëà
ò ê äåëèò ñÿ í à êâàäðàò ï ðî ñò î ãî ÷èñëà
ò ê ïðîñòîå÷èñëî
μ
μ
μ
μ
μ
=
=− =
==
=− = → =−
=
2
.. 1 0 2 5 (ï ðî èçâåäåí èå äâóõ ï ðî ñòû õ ÷èñåë),
k2 (-1) 1
òê =⋅
=→ =
Перейдем к рассмотрению вопросов построения неприво-
димых многочленов.
Ранее мы определили число нормированных многочленов
данной степени
n в кольце
][xF
q
. Получим теперь формулу для
произведения всех нормированных неприводимых многочленов
данной степени
n из кольца
][xF
q
.
Теорема (*). Пусть
),,(
x
nq
I
произведение всех нормиро-
ванных неприводимых многочленов степени
n из кольца
][xF
q
.
66
Тогда оно определяется формулой
∏
−=
nd
dq
xxxnqI
dn
/
)(
)(),,(
/
μ
Пример
: q=2, n=4. Здесь d=1,2,4.
16 (1)4 (2)2 (4)
16 15
16 14 12 0
43
12 9 6 3
(2,4;)( )()()
1
( )()()
1
1
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
12 9
9
96
6
63
1 | 1
1
1
1
1
xx
xxxxxx
x
xx
x
xx
x
xx
−−
−
++++
−
−
−
−
−
−
3
3
1
1
0
x
x
−
−
Все нормированные неприводимые многочлены степени
n
из
][xF
q
можно найти, различая на множители многочлен
);,(
x
nq
I
. В этой связи было бы полезно представить
);,(
x
nq
I
в
частично разложенном виде. Этого можно добиться, опираясь на
следующие факты.
Теорема. Для поля F характеристики p и натурального
числа
n, не делящегося на р, n - круговой многочлен
)(xQ
n
над
F задается выражением:
∏
−=
nd
ddn
n
xxQ
/
)(/
)1()(
μ
(1)
Отсюда имеет место теорема.
Теорема. Пусть
);,(
x
nq
I
тоже, что и в теореме (*). Тогда

Страницы