ВУЗ:
Составители:
Рубрика:
61
Определение. Пусть f(x)
∈
F
q
[x] ненулевой многочлен. Если
f(0)
≠
0, то наименьшее натуральное число е, для которого много-
член
f(x) делит (x
e
-1) называется порядком многочлена f(x) и
обозначается
ord(f(x)). Если же f(0)=0, то многочлен f(x) одно-
значно представим в виде
f(x)=x
h
g(x) где h
∈
N, g(x)
∈
F
q
[x] и
g(0)=0 и тогда ord(f(x)) многочлена f(x) определяется как
ord(g(x)).
Порядок многочлена иногда называют его
периодом или
экспонентой многочлена. Порядок неприводимого многочлена
можно определить, пользуясь следующей теоремой.
Теорема. Пусть f(x)
∈
F
q
[x] неприводимый многочлен сте-
пени
m, удовлетворяющий условию f(0)
≠
0. Порядок этого мно-
гочлена совпадает с порядком любого корня этого многочлена в
мультипликативной группе
F* поля F
q
m
.
Отсюда вытекает важное следствие: Если
f(x)
∈
F
q
[x] не-
приводимый многочлен степени
m над полем F
q
, то его порядок
ord(f(x)) делит число q
m
-1.
Значения порядков многочленов играют важную роль при
формировании линейных рекуррентных псевдослучайных по-
следовательностей над конечными полями и кольцами, которые
в свою очередь являются основой для создания поточных крип-
тосистем.
Так как каждый многочлен положительной степени можно
записать в виде произведения неприводимых многочленов (ка-
ноническая форма представления многочленов), то вычисление
порядков
многочленов значительно упрощается если знать, как
находить порядок неприводимого многочлена и произведения
попарно взаимно простых многочленов. Ответ на этот вопрос
дают следующие теоремы.
Лемма. Пусть с – натуральное число. Многочлен
f(x)
∈
F
q
[x], удовлетворяющий условию f(0)
≠
0 делит двучлен x
c
-
1 тогда и только тогда, когда ord(f(x)) делит число с.
Следствие. Если е
1
и е
2
натуральные числа, то НОД мно-
гочленов (
x
e1
-1) и (x
e2
-1) в F
q
[x] равен (x
d
-1), где d=НОД(е
1
, е
2
).
Теорема. Пусть n
∈
N и g(x) – неприводимый многочлен
над конечным полем характеристики
P, такой что g(0)
≠
0. Тогда
62
для многочлена вида
f(x)=g
n
(x) имеем
ord(f(x))=ord(g
n
(x))=p
t
ord(g(x)),
где
t – наименьшее целое число, для которого p
t
≥
n.
Теорема. Пусть g
1
(x),...,g
k
(x) – попарно взаимно простые
ненулевые многочлены над полем
F
q
, и пусть
f(x)=g
1
(x)
⋅
g
2
(x)...g
K
(x), тогда
ord(f(x))=ord(g
1
(x))
⋅
ord(g
K
(x))=НОК(ord(g
1
(x),...,ord(g
K
).
Иными словами, порядок произведения попарно взаимно про-
стых ненулевых многочленов равен наименьшему общему крат-
ному порядков его сомножителей (многочленов).
Пример:
f(x)=x
10
+x
9
+x
3
+x
2
+1
∈
F
2
[x].
Каноническое разложение
f(x) над полем F
2
имеет вид
f(x)=(x
2
+x+1)
3
(x
4
+x+1). Т.к. ord(x
2
+x+1)=3 и имея
ord(g
n
(x)=p
t
ord(g(x)), получаем, что ord((x
2
+x+1)
3
)=2
2
⋅
3=12 т.к. у
нас
F
2
т.е. p=2 и t=2 чтобы 2
2
>3). Далее ord(x
4
+x+1)=15. Тогда
ord(f(x))=НОК(12,15)=60.
Обобщить эти результаты можно теоремой.
Теорема. Пусть F
q
конечное поле характеристики p. Если
nK
K
n
ffaf ⋅⋅⋅= ...
1
1
каноническое разложение в кольце F
q
[x] мно-
гочлена
f(x)
∈
F
q
[x] положительной степени, такого что f(0)
≠
0, то
))(,...),(()...())((
1
1
1 K
tnK
K
n
fordfordНОКpfafordxford =⋅⋅=
,
где
t – наименьшее целое число, удовлетворяющее нера-
венству
p
t
≥
max{n
1
,...,n
K
}.
Из определения порядка
е многочлена f(x) следует, что е
это наименьшее натуральное число, удовлетворяющее сравне-
нию:
x
e
≡
1(mod(f(x)),
т.к. это сравнение означает, что
f(x) делит x
e
-1. Отсюда следует
еще один способ определения порядка многочленов. Согласно
приведенному выше следствию 1 порядок е делит число
q
m
-1,
где
m степень многочлена f(x). Предполагая q
m
>2 будем исхо-
дить из разложения числа
q
m
-1 на простые сомножители:
∏
=
=−
S
j
r
j
m
j
pq
1
1
.
Для каждого Sj
≤
≤
1 найдем вычеты одночлена
j
m
pq
x
/)1( −
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
