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

UptoLike

ВУЗ: 

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

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

Рубрика: 

41
[0]={..., –2n; -n, 0, n, 2n, ...}
[1]={..., -2n+1, -n+1, 1, n+1, 2n+1, ...}
[n -1]={..., -n -1, -1, n -1, 2n -1, 3n -1, ...}
Определение. Группа, образованная множеством { [0], [1],
... ,[n -1]} классов вычетов по модулю n с операцией
[a]+[b]=[a+b], называется группой классов вычетов по модулю
n и обозначается Z
n
.
Группа
Z
n
является циклической с образующим элементом
[1] и имеет порядок n.
Определение. Группа называется конечной (бесконечной),
если она состоит из конечного (бесконечного) числа элементов.
Число элементов конечной группы
G называется ее порядком и
обозначается
|
G
|
.
Удобным способом задания конечной группы является их
представление в виде таблицы групповой операции (таблицы
Кэли), которая строится так: ее строки и столбцы помечаются
элементами группы и на пересечении строки, помеченной эле-
ментом
а и столбца, помеченного элементом b, ставится элемент
аb.
Пример:
Таблица Кэли группы
Z
6
классов вычетов по модулю 6.
+ [0][1][2][3][4][5]
[0]
[1]
[2]
[3]
[4]
[5]
[0][1][2][3][4][5]
[1][2][3][4][5][0]
[2][3][4][5][0][1]
[3][4][5][0][1][2]
[4][5][0][1][2][3]
[5][0][1][2][3][4]
Эта группа Z
6
представляет собой:
Пусть
G - множество остатков {0, 1, 2, 3, 4, 5} от деления
целых чисел из
Z на 6 и для чисел а и b из G величина а*b пусть
остаток от деления на
6 обычной суммы а + b. Тогда получим
группу
Z
6
.
Каждая группа содержит некоторые подмножества , кото-
рые сами образуют группу с той же групповой операцией.
Определение. Подмножества Н группы G называется под-
42
группой этой группы, если
Н само образует группу относитель-
но операций группы.
Примером группы является следующее определение.
Определение. Подгруппа группы G ,состоящая из всех
степеней элемента
а этой группы, называется подгруппой, по-
рожденной элементом а и обозначается <а>.
Если подгруппа
<а> конечна, то ее порядок называется по-
рядком элемента а. а
1
, а
2
, ... а
n
.
Приведем следующую теорему, доказательство которой
тривиально.
Теорема. Если Н - подгруппа группы G, то отношение R
H
на
G определяемое условием
(а,b)
∈
R↔a=bh
для некоторого
h
∈
H, является отношением эквивалентно-
сти.
Соответствующие отношению
R
n
классы эквивалентности
называются
левыми смежными классами группы G по под-
группе
H и обозначаются
aH={ah
|
h
∈
H} для мультипликативной группы
или
a + H ={a+h
|
h
∈
H} для аддитивной группы
где
а – фиксированный элемент группы G.
Аналогично определяется разбиение группы
G на правые
смежные классы по подгруппе
H
Ha={ha
|
h
∈
H}.
Если
G – абелева группа, то ее левые смежные классы по
подгруппе
H совпадают с правыми, а сама подгруппа Н нор-
мальная.
Пример.
Пусть G
12
={[0],[1],[2],...,[11]} и пусть H подгруппа
H={[0],[3],[6],[9]}. Тогда различными (левыми) смежными
классами
G по H являются
[0] + H = {[0],[3],[6],[9]}
[1] + H = {[1],[4],[7],[10]}
[2] + H = {[2],[5],[8],[11]}.
Теорема. Если H - конечная подгруппа группы G, то каж-
дый (левый или правый) смежный класс группы
G по подгруппе

Страницы