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

UptoLike

ВУЗ: 

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

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

Рубрика: 

39
использовано мультипликативное обозначение, как для обычно-
го умножения. Тогда вместо
а*b можно просто записать а
⋅
b или
аb . Однако при этом не предполагается, что операция * -это
простое умножение. В ряде случаев для групповой операции
*
может быть использована аддитивная запись
а+b вместо а*b.
Тогда элемент группы
G а+b называют суммой элементов а,b и
0 вместо е (единичный элемент в мультипликативной записи ) и
-а вместо a
-1
. Такие обозначения обычно используются для абе-
левых групп.
Если
а
∈
G и n
∈
N в мультипликативной записи пишут a
n
= a
⋅
a ... a (n сомножителей a) и элемент a
n
называют n
й
степе-
нью числа
а.
Если для групповой операции используется
+ т.е. аддитив-
ное обозначение, то вместо
a
n
будем иметь nа=а + а + ... + а (n
слагаемых
а).
Используя мультипликативные и аддитивные обозначения
в общем случае имеем следующие правила:
Мультипликативные
обозначения
Аддитивные
обозначения
a
-n
= (a
-1
)
n
( -n)а=n( -а)
a
m
a
n
= a
m+n
mа+nа=(m+n)а
(a
m
)
n
= a
m
⋅
n
m(nа)=(m
⋅
n)а
Для n=0
∈
Z имеем
a
0
= e в мультипликативных обозначениях и 0
⋅
а=0 в адди-
тивных обозначениях.
Группы
G, использующие указанные формы записи назы-
вают
мультипликативными и аддитивными.
Примеры.
1)
Пусть G - множество целых чисел с операцией + (сло-
жение). Известно, что данная операция, т.е. сумма двух целых
чисел однозначно определяет целое число. Эта группа
G, еди-
ничным элементом которой является
0, а обратным для целого
числа
а является число -а . Такую группу обозначают через Z.
2)
Множество, состоящее из единственного элемента е с
операцией
* , определенной условием е*е=е является группой.
Определение. Мультипликативная группа G называется
40
циклической, если в ней имеется такой элемент а , что каждый
элемент
b
∈
G является степенью элемента а т.е. существует це-
лое число
К такое, что b = a
K
. Этот элемент а называется обра-
зующим элементом группы G . Для циклической группы G
применяют обозначение G=<а>.
Из определения следует, что циклическая группа является
коммутативной или абелевой.
В аддитивной циклической группе
Z b=ка может быть бо-
лее одного образующего элемента, например
1 и –1.
Отношением эквивалентности на множестве S называ-
ется подмножество
R множества S
×
S упорядоченных пар (s,t)
s,t
∈
S обладающее тремя свойствами:
1.
(s,s)
∈
R для всех s
∈
S (рефлективностью)
2. Если
(s,t)
∈
R , то (t,s)
∈
R (симметричностью)
3. Если
(s,t) ,(t,v)
∈
R, то (s,v)
∈
R (транзитивностью)
Элементы
s,t
∈
S называются эквивалентными, если
(s,t)
∈
R. Простейшим примером отношения эквивалентности яв-
ляется равенства
s=t:
1. s=s, t=t
∈
R
2. s=t → t=s ∈ R
3. s=t, t=v → s=v ∈ R
Отношение эквивалентности на множестве S разбивает это
множество
S на попарно непересекающиеся подмножества, объ-
единяя все элементы множества
S, эквивалентные некоторому
фиксированному элементу
s
∈
S получим класс эквивалентности
элемента
s, который обозначается:
[s]={t
∈
S
|
(s,t)
∈
R}.
Совокупность всех различных классов эквивалентности да-
ет указанное выше разбиение множества
S на попарно непересе-
кающиеся подмножества (
классы эквивалентности).
Как уже отмечалось на прошлой лекции, важным классом
эквивалентности на множестве целых чисел является отношение
сравнимости чисел
а и b (a,b
∈
z) по модулю n. a
≡
b(mod n).
Классы эквивалентности, на которые отношение сравнимо-
сти по модулю
n разбивает множество целых чисел Z, называют
классами вычетов по модулю n. Ими являются:

Страницы