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

UptoLike

ВУЗ: 

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

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

Рубрика: 

63
по модулю
f(x) (т.е. остатки от их деления на f(x)). Обычно это
делается перемножением подходящим образом выбранного на-
бора вычетов по модулю f(x) степеней
12
,...,,,
−m
gqq
xxxx
пере-
менной
x. При этом, если
))(mod(1
/)1(
xfx
j
m
pq
≠
−
,то число е де-
лится на
j
r
j
p , в противном случае, число е не делится на
j
r
j
p . В
последнем случае мы выясняем, будет ли число е делится на
1−
j
r
j
p ,
2−
j
r
j
p , ...,
j
p , вычисляя соответственно вычеты по модулю
f(x) следующих степеней переменной x:
2
/)1(
j
m
pq
x
−
,
3
/)1(
j
m
pq
x
−
,...,
j
r
j
m
pq
x
/)1( −
. Такой подсчет проводится для каждого
простого делителя
p
j
числа q
m
-1 и в итоге находится порядок
e=ord(f(x)).
В этом методе ключевым моментом является разложение
на простые сомножители натурального числа
q
m
-1. Существуют
обширные таблицы для полного такого разложения указанных
чисел, особенно для
q=2 т.е. для полей F
2
и F
2
m
.
64
7. Элементы теории конечного поля.
Многочлены над конечными полями.
Определение. Многочлен
][)( xFxf
q
∈
степени
1≥m
на-
зывается примитивным многочленом над полем
q
F , если он яв-
ляется минимальным многочленом над
q
F некоторого прими-
тивного элемента расширения
qm
F
поля
q
F .
Это определение опирается на приведенные, на прошлой
лекции понятия примитивного элемента и означает, что прими-
тивный многочлен над
q
F степени m - это нормированный мно-
гочлен который неприводим над
q
F и имеет корень
qm
Fa ∈
,
который является образующим мультипликативной группы
qm
F
*
поля
qm
F .
Теорема. Многочлен
][)( xFxf
q
∈
степени m является
примитивным тогда и только тогда, когда он нормирован и, та-
кой, что
1q)) ord(f(x 0)0(
m
−=≠ иf
.
Рассмотрим теперь вопрос о числе нормированных непри-
водимых многочленов над конечным полем
q
F .
Теорема. Для каждого конечного поля
q
F и каждого n
∈Ν
произведение всех нормированных неприводимых многочленов
над
q
F , степень которых делит n, равно
x
x
n
q
−
.
Следствие: Если
)(dN
q
число нормированных неприво-
димых многочленов из
][xF
q
степени d, то
∑
=
nd
q
n
ddNq
/
)(
для
всех
n, где суммирование берется по всем положительным дели-
телем
d числа n.
Из последнего выражения, используя арифметическую
функцию Мебиуса можно получить точную формуле для числа
нормированных неприводимых многочленов фиксированной

Страницы