1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
\documentclass[a4paper,oneside]{article}
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{amsthm}
\usepackage{minted}
\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{float}
\newtheorem{theorem}{Теорема}
\newtheorem*{theorem*}{Теорема}
% --- Определение --- %
\theoremstyle{definition}
\newtheorem{definition}{Определение}
\newtheorem*{definition*}{Определение}
% ------------------- %
\theoremstyle{definition}
\newtheorem*{example}{Пример}
\title{{Криптографические методы защиты информации}\\{Лабораторная работа №6}}
\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}
\date{\the\year{} г.}
\begin{document}
\maketitle
\begin{definition}
\textbf{Группа} --- непустое множество, на котором определена ассоциативная
бинарная операция, причём для этой операции имеется нейтральный элемент, и
каждый элемент множества имеет обратный.
\end{definition}
\begin{definition}
\textbf{Циклическая группа} --- группа $(G, \cdot)$, которая может быть
порождена одним элементом $a$, то есть все её элементы являются степенями
$a$. Обозначается как $G = \langle a \rangle$.
\end{definition}
\begin{definition}
\textbf{Подгруппа} --- подмножество $H$ группы $G$, которое является группой
относительно операции, определённой в $G$.
\end{definition}
\begin{theorem}
\label{thm:all_cycle}
Каждая подгруппа циклической группы является циклической.
\end{theorem}
\begin{proof}
Допустим, $G = \langle g \rangle = \{ g^k : k \in \mathbb{Z} \}$ ---
циклическая группа. Пусть $H$ --- подгруппа $G$. Если $H = \{ 1 \}$, то
$H$ --- циклическая. Положим, что $H$ --- нетривиальная подгруппа и пусть
$g^k \in H$, где $g^k \neq 1$. Тогда, так как $H$ является подгруппой,
$g^{-k} = (g^k)^{-1} \in H$. Получаем, что $H$ содержит положительную
степень числа $g$, отличную от 1. Возьмём минимальное положительное $m$
такое, что $g^m \in H$. Очевидно, что все степени $g^m$ также принадлежат
$H$, то есть $\langle g^m \rangle \subseteq H$.
Докажем, что это выражение является равенством. Пусть $g^k$ является
любым элементом $H$. Мы можем выразить $k = qm + r$, где $0 \leq r < m$.
Но $g^k = g^{qm + r} = g^{qm} g^r = (g^m)^q g^r$. Получаем
\begin{equation*}
g^r = (g^m)^{-q} g^k \in H
\end{equation*}
Так как $m$ --- минимальное положительное целое число такое, что $g^m \in
H$ и при этом $0 \leq r < m$, следует, что $r = 0$. Тогда,
$g^k = (g^m)^q \in \langle g^m \rangle$. Таким образом, мы показали, что
$H \subseteq \langle g^m \rangle \implies H = \langle g^m \rangle$.
Получаем, что $H$ --- цикличная с порождающим элементом $g^m$, где $m$ ---
минимальное положительное целое число, для которого справедливо $g^m \in H$.
\end{proof}
\begin{theorem}[Фундаментальная теорема конечных цикличных групп]
Пусть $G = \langle g \rangle$ --- цикличная группа порядка $n$. Тогда,
\begin{enumerate}
\item
Если $H$ --- подгруппа $G$, то $H = \langle g^d \rangle$ для
некоторого $d \mid n$.
\item Если $H$ --- подгруппа $G$ и $|H| = k$, то $k \mid n$.
\item
Если $k \mid n$, то $\langle g^{n/k} \rangle$ --- единственная
подгруппа $G$ порядка $k$.
\end{enumerate}
\end{theorem}
\begin{proof}
\begin{enumerate}
\item \label{thm:fund_1}
По Теореме \ref{thm:all_cycle}, $H$ --- циклическая группа.
Так как $|G| = n < \infty \implies H = \langle g^m \rangle$, где
$m > 0$. Пусть $d = \gcd(m, n)$. Так как $d \mid n$, достаточно
показать, что $H = \langle g^d \rangle$. Но $d \mid m$, поэтому
$m = qd$. Тогда $g^m = (g^d)^q \implies g^m \in \langle g^d \rangle$.
Таким образом, $H = \langle g^m \rangle \subseteq \langle g^d \rangle$.
Но $d = rm + sn$, где $r, s \in \mathbb{Z}$, поэтому
\begin{equation*}
g^d = g^{rm + sn} = g^{rm} g^{sn} = (g^m)^r (g^n)^s =
(g^m)^r (1)^s = (g^m)^r \in \langle g^m \rangle = H
\end{equation*}
Получаем, что $\langle g^d \rangle \subseteq H \implies
\langle g^d \rangle = H$.
\item
В следствие пункта \ref{thm:fund_1}, $H = \langle g^d \rangle$,
где $d \mid n$. Тогда $k = |H| = n / d$. Получаем, что $k \mid n$.
\item
Допустим $K$ --- подгруппа $G$ порядка $k$. По пункту \ref{thm:fund_1},
пусть $K = \langle g^m \rangle$, где $m \mid n$. $k = |K| = |g^m|
= n/m$. Получаем $m = n/k \implies K = \langle g^{n/k} \rangle$.
\end{enumerate}
\end{proof}
\begin{example}
Пусть $G = \mathbb{Z}_6 = \{ 0, 1, 2, 3, 4, 5 \}$ --- кольцо вычетов по
модулю 6. Вычислим все подгруппы, беря каждый из элементов как порождающий.
\begin{align*}
H_0 &= \{ 0 \} \\
H_1 &= \{ 0, 1, 2, 3, 4, 5 \} = G \\
H_2 &= \{ 0, 2, 4 \} \\
H_3 &= \{ 0, 3 \} \\
H_4 &= \{ 0, 2, 4 \} = H_2 \\
H_5 &= \{ 0, 1, 2, 3, 4, 5 \} = H_1 = G
\end{align*}
Делителями числа 6 являются $\{ 1, 2, 3, 6 \}$. Можно заметить, что для
каждого из делителей существует единственная уникальная подгруппа
соответствующего порядка (для 1 --- $\langle 0 \rangle$, для 2 ---
$\langle 3 \rangle$, для 3 --- $\langle 2 \rangle$, для 6 --- $G$).
\end{example}
\end{document}
|
