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

UptoLike

ВУЗ: 

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

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

Рубрика: 

59
Если
K простое подполе поля F, то )(
/
aT
KF
r
называют аб-
солютным следом элемента a и обозначают )(aT
F
r
.
Иными словами
след )(
/
aT
KF
r
элемента а над полем K есть
сумма всех сопряженных с
а относительно K элементов.
Дадим
еще одно определение следа. Пусть f(x)
∈
K[x] ми-
нимальный многочлен элемента
a
∈
F над полем K. Его степень d
является делителем числа
m. Назовем многочлен g(x)=f(x)
m/d
из
K[x] характеристическим многочленом элемента а над полем
К. Согласно представленной выше теореме Галуа корнями мно-
гочлена
f(x) в поле F являются элементы
1
,...,,
−d
qq
aaa , поэтому
получаем, что корнями многочлена
g(x) в поле F являются эле-
менты, которые сопряжены с элементом а относительно поля
K.
Отсюда
))...()((...)(
1
0
1
1
−
−−−=+++=
−
−
m
qqm
m
m
axaxaxaxaxxg
и сравнение коэффициентов дает
1
)(
/
−
−
=
mr
aaT
KF
.
Этот след всегда является элементом поля
К.
Определение. Для a
∈
F=F
q
m
и K=F
q
определим норму
N
F/K
(a) элемента а над полем К равенством
)1/()1(
/
12
...)(
−−
=⋅⋅⋅⋅=
=
qqqqq
KF
mm
aaaaaaN .
Через свободный член
0
a характеристического многочлена
элемента
а над полем К:
0/
)1()( aaN
KF
−= .
Определение. Пусть К конечное поле и F его конечное
расширение. Тогда два базиса {
a
1
,...,a
m
} и {b
1
,...,b
m
} поля F над
К называется дуальными, если для mji
≤
≤ ,1
⎩
⎨
⎧
=
≠
=
ji
ji
baN
iir
KF
1
0
)(
/
.
Определение. Пусть K=F
q
и F=F
q
m
. Тогда базис поля F над
К вида },...,,,{
12 −m
qqq
aaaa состоящий из подходящим образом
выбранного элемента
a
∈
F и сопряженных с ним относительно
поля
К элементов, называют нормальным базисом поля F над К.
Пример:
Пусть a
∈
F
8
корень неприводимого многочлена
x
3
+x
2
+1 из F
2
[x]. Тогда {a,a
2
,(1+a+a
2
)} - базис поля F
8
над F
2
.
60
Однозначно определенным к нему дуальным базисом (в данном
случае автодуальным) будет этот же базис. Действительно эле-
мент
a
5
∈
F
8
можно представить в виде
a
5
=c
1
a+c
2
a
2
+c
3
(1+a+a
2
),
где коэффициенты c
1
, c
2
, c
3
из F
2
определяются
888
525 25
123
()0; ( )1; ((1 ))1
FFF
rrr
cTaa cTaa cT aaa=⋅= = ⋅= = ++ =
так
, что a
5
=a
2
+(1+a+a
2
).
Указанный базис является также нормальным базисом по-
ля
F
8
над F
2
, т.к. 1+a+a
2
=a
4
. Чтобы разобраться в представлен-
ном выше примере рассмотрим один из способов представления
элементов конечного поля
F
q
из q=p
2
элементов. Идея этого спо-
соба базируется на следующих фактах: Поле
F
q
является про-
стым алгебраическим расширением простого поля
F
p
. Если f(x)
неприводимый многочлен степени
n из F
p
[x] , то любой корень а
этого многочлена принадлежит полю
F
p
n
=F
q
и потому F
q
=F
p
(a).
Тогда каждый элемент поля
F
q
можно однозначно представить в
виде значения некоторого многочлена от х над
F
p
степени не бо-
лее
n -1, при x=a.
Например, чтобы представить таким способом элементы
поля
F
9
будем рассматривать это поле как простое алгебраиче-
ское расширение степени 2 поля
F
3
, которое получается присое-
динением корня а неприводимого над
F
3
многочлена степени 2,
пусть это будет
f(x)=x
2
+1
∈
F
3
[x]. Тогда f(a)=a
2
+1=0 в F
9
и девять
элементов поле
F
9
можно задать в виде: p
0
+p
1
a, где p
0
,p
1
∈
F
3
.
Точнее,
F
9
={0,1,2,a,1+a,2+a,2a,1+2a,2+2a}.
Продолжим теперь более детальное рассмотрение элемен-
тов теории многочленов над конечными полями ввиду важности
ее приложений в криптографии.
У каждого ненулевого многочлена
f(x) над конечным по-
лем кроме его степени
deg(f(x)) имеется еще одна важная цело-
численная характеристика – его порядок.
Лемма. Если f(x)
∈
F
q
[x] многочлен степени m
≥
1, удовле-
творяющий условию
f(0)
≠
0, то существует натуральное число
1
−≤
m
qe , для которого двучлен x
e
-1 делится на f(x).
Этот факт позволяет ввести определение порядка много-
члена над конечным полем.

Страницы