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

UptoLike

ВУЗ: 

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

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

Рубрика: 

47
Идеал
J кольца R называется главным, если существует
элемент
a
∈
R, такой что J=(a). Здесь, для коммутативного кольца
R, величина (a)={ra+na
|
r
∈
R, n
∈
Z} - наименьший идеал, содер-
жащий данный элемент
a
∈
R. Если кольцо имеет единицу, то (a)
={ra
|
r
∈
R} ((a) - главный идеал).
Пример.
Пусть p=3 простое число. Тогда факторкольцо со-
стоит из трех элементов
[0],[1],[2]. Операции в этом кольце
можно задать таблицами, аналогичными таблицам Кэли конеч-
ных групп
+ [0][1][2]
⋅
[0][1][2]
[0]
[1]
[2]
[0][1][2]
[1][2][3]
[2][3][4]
[0]
[1]
[2]
[0][0][0]
[0][1][2]
[0][2][1]
Приведенный пример является первым рассматриваемым
нами образцом
конечного поля, т.е. поля, содержащего конечное
число элементов, которые играют основную роль в современной
криптографии.
48
5. Элементы теории конечного поля. Основные
понятия и теоремы.
Поле.
Определение. Отображение
ϕ
: R
→
S кольца R в кольцо S
называется
гомоморфизмом, или для любых a,b
∈
R
ϕ
(a+b)=
ϕ
(a)+
ϕ
(b) и
ϕ
(ab)=
ϕ
(a)
ϕ
(b).
Таким образом, гомоморфизм
ϕ
: R
→
S сохраняет обе опе-
рации
+ и
⋅
. кольца R.
Определение. Для простого числа Р обозначим через F
P
множества
{0,1,2,...,P -1} целых чисел, и пусть отображение
ϕ
:
Z/p
→
F
p
определяется условием
ϕ
([a])=a для a=0,1,2,...,P -1. То-
гда множество
F
P
со структурой поля, индуцированной отобра-
жением
ϕ
, называется полем Галуа порядка P. (Такое поле еще
обозначают
GF(p) – аббревиатура от слов Galois и Field(поле)).
Отображение
ϕ
: Z/p
→
F
p
является изоморфизмом т.к.
ϕ
([a]+[b])=
ϕ
([a])+
ϕ
([b]) и
ϕ
([a]
⋅
[b])=
ϕ
([a])
⋅
ϕ
([b]). Нулем
конечного поля
GF
p
будет 0 ноль, а единицей – единица 1 и его
структура совпадает со структурой поля
Z/p.
Пример.
Важным является пример конечного поля GF
p
второго порядка. Элементами этого поля являются
0 и 1 - бинар-
ные элементы, для которых выполняются операции
⊕
0 1
⋅
0 1
0
1
0 1
1 0
0
1
0 0
0 1
В связи с использованием для вычислений ЭВМ не менее
важным является поле Галуа из элементов
{0,1}, обозначаемое
GF(2
N
) и соответствующие строкам данных длиной N бит. Такие
строки бит удобно рассматривать в виде многочленов. Напри-
мер, байт из 8 бит можно представить
(10010101)=x
7
+x
4
+x
2
+1.
Определение. Пусть R произвольное кольцо. Если сущест-
вует такое натуральное число
n, что для каждого r
∈
R выполня-
ется равенство
n
⋅
r=0, то наименьшее из таких чисел n (напри-
мер,
n
0
) называется характеристикой кольца R, а само R назы-
вают
кольцом характеристики n
0
.

Страницы