forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
groups.tex
188 lines (154 loc) · 12.6 KB
/
groups.tex
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
\section{Группы}
\selectlanguage{russian}
\subsection{Свойства групп}
\textbf{Группой}\index{группа} называется множество $\Gr$, в котором задана операция $\centerdot$ между двумя элементами группы и удовлетворяются аксиомы:
\begin{enumerate}
\item замкнутость
\[ \forall a,b \in \Gr: a \centerdot b = c \in \Gr; \]
\item ассоциативность
\[ \forall a,b,c \in \Gr: (a \centerdot b) \centerdot c = a \centerdot (b \centerdot c); \]
\item существование единичного элемента
\[ \exists ~ e \in \Gr: e\centerdot a = a \centerdot e = a; \]
\item существование обратного элемента
\[ \forall a \in \Gr ~ \exists ~ b \in \Gr: a \centerdot b = b \centerdot a = e. \]
\end{enumerate}
Если
\[ \forall a,b \in \Gr: a \centerdot b = b \centerdot a, \]
то группа коммутативная.
Если операция в группе задана как умножение $\cdot$, то группа называется \textbf{мультипликативной}, $e = 1$, обратный элемент -- $a^{-1}$, возведение в степень $k$ -- $a^k$.
Если операция задана как сложение $+$, то группа называется \textbf{аддитивной}, $e = 0$, обратный элемент $-a$, сложение $k$ раз -- $ka$.
Подмножество группы, удовлетворяющее аксиомам группы, называется \textbf{подгруппой}\index{подгруппа}.
\textbf{Порядком} $|\Gr|$ \textbf{группы}\index{порядок группы} $\Gr$ называется число элементов в группе. Пусть группа мультипликативная. Для любого элемента $a \in \Gr$ выполняется $a^{|\Gr|} = 1$.
\textbf{Порядком элемента} $a$ называется минимальное число
\[ ord(a): a^{ord(a)} = 1 \]
Порядок элемента делит порядок группы:
\[ ord(a) \divides |\Gr|. \]
\subsection{Циклические группы}
\textbf{Генератором} $g \in \Gr$ называется элемент, \emph{порождающий} всю группу\index{генератор группы}
\[ \Gr = \{g, g^2, g^3, \ldots, g^{|\Gr|} = 1\}. \]
Группа, в которой существует генератор, называется \textbf{циклической}\index{группа!циклическая}.
Если конечная группа не циклическая, то в ней существуют циклические подгруппы, порожденные всеми элементами. Любой элемент $a$ группы порождает либо циклическую \emph{подгруппу}
\[ \{ a, a^2, a^3, \dots, a^{ord(a)} = 1 \} \]
порядка $ord(a)$, если порядок элемента $ord(a) < |\Gr|$, или \emph{всю} группу
\[ \Gr = \{ a, a^2, a^3, \dots, a^{|\Gr|} = 1 \}, \]
если порядок элемента равен порядку группы $ord(a) = |\Gr|$. Порядок любой подгруппы, как и порядок элемента, делит порядок всей группы.
Представим циклическую группу через генератор $g$ как
\[ \Gr = \{g, g^2, \ldots, g^{|\Gr|} = 1\} \]
и каждый элемент $g^i$ возведем в степени $1, 2, \ldots, |\Gr|$. Тогда
\begin{itemize}
\item элементы $g^i$, для которых число $i$ взаимно просто с $|\Gr|$, породят снова всю группу
\[ \Gr = \{ g^i, g^{2i}, g^{3i}, \dots, g^{|\Gr| i} = 1 \}, \]
так как степени $\{i, 2i, 3i, \dots |\Gr| i \}$ по модулю $|\Gr|$ образуют перестановку чисел $\{1, 2, 3, \dots, |\Gr|\}$; следовательно, $g^i$ -- тоже генератор, число таких чисел $i$ по определению функции Эйлера $\varphi(|\Gr|)$ ($\varphi(n)$ -- количество взаимно простых с $n$ целых чисел в диапазоне $[1,n-1]$);
\item элементы $g^i$, для которых $i$ имеют общие делители
\[ d_i = \gcd(i, |\Gr|) \neq 1 \]
c $|\Gr|$, породят подгруппы
\[ \{ g^i, g^{2i}, g^{3i}, \dots, g^{\frac{i}{d_i} |\Gr|} = 1\}, \]
так как степень последнего элемента кратна $|\Gr|$; следовательно, такие $g^i$ образуют циклические подгруппы порядка $d_i$.
\end{itemize}
%TODO Гашков, Болотов, Часовских "эллиптическая криптография" или "методы элл. кри-ии"
Из предыдущего утверждения следует, что число генераторов в циклической группе равно
\[ \varphi(|\Gr|). \]
Для проверки, является ли элемент генератором всей группы, требуется знать разложение порядка группы $|\Gr|$ на множители. Далее элемент возводится в степени, равные всем делителям порядка группы, и сравнивается с единичным элементом $e$. Если ни одна из степеней не равна $e$, то этот элемент является примитивным элементом или генератором группы. В противном случае элемент будет генератором какой-либо подгруппы.
Задача разложения числа на множители является трудной для вычисления. На сложности ее решения, например, основана криптосистема RSA\index{криптосистема!RSA}. Поэтому при создании больших групп желательно заранее знать разложение порядка группы на множители для возможности выбора генератора.
\subsection{Группа $\Z_p^*$}
\textbf{Группой $\Z_p^*$} называется группа\index{группа!$\Z_p^*$}
\[ \Z_p^* = \{1, 2, \dots, p-1 \mod p\}, \]
где $p$ -- простое число, операция в группе -- умножение $\ast$ по $\mod p$.
Группа $\Z_p^*$ -- \textbf{циклическая}, порядок
\[ |\Z_p^*| = \varphi(p) = p - 1. \]
Число генераторов в группе --
\[ \varphi(|\Z_p^*|) = \varphi(p-1). \]
Из того, что $\Z_p^*$ -- группа, для простого $p$ и любого $a \in [2, p-1] \mod p$ следует \textbf{малая теорема Ферма}\index{теорема!Ферма малая}:
\[ a^{p-1} = 1 \mod p. \]
На малой теореме Ферма основаны многие тесты проверки числа на простоту.
\example
Рассмотрим группу $\Z_{19}^*$. Порядок группы -- 18. Делители: 2, 3, 6, 9. Является ли 12 генератором?
\[ \begin{array}{l}
12^2 = -8 \mod 19, \\
12^3 = -1 \mod 19, \\
12^6 = 1 \mod 19, \\
\end{array} \]
12 -- генератор подгруппы 6 порядка. Является ли 13 генератором?
\[ \begin{array}{l}
13^2 = -2 \mod 19, \\
13^3 = -7 \mod 19, \\
13^6 = -8 \mod 19, \\
13^9 = -1 \mod 19, \\
13^{18} = 1 \mod 19, \\
\end{array} \]
13 -- генератор всей группы.
\exampleend
\example
В таб. \ref{tab:Zp-sample} приведен пример группы $\Z_{13}^*$. Число генераторов -- $\varphi(12) = 4$. Подгруппы --
\[ \Gr^{(1)}, \Gr^{(2)}, \Gr^{(3)}, \Gr^{(4)}, \Gr^{(6)}, \]
верхний индекс обозначает порядок подгруппы.
\begin{table}[h!]
\centering
\caption {Генераторы и циклические подгруппы группы $\Gr=\Z_{13}^*$\label{tab:Zp-sample}}
\resizebox{\textwidth}{!}{ \begin{tabular}{|c|p{0.66\textwidth}|c|}
\hline
Элемент & Порождаемая группа или подгруппа & Порядок \\
\hline
1 & $\Gr^{(1)} = \{ 1 \}$ & 1 \\
2 & $\Gr = \{ 2, 4, 8 = -5, -10 = 3, 6, 12 = -1, -2, -4, -8 = 5, 10 = -3, -6, -12 = 1 \}$ & 12, ген. \\
3 & $\Gr^{(3)} = \{ 3, 9 = -4, -12 = 1 \}$ & 3 \\
4 & $\Gr^{(6)} = \{ 4, 16 = 3, 12 = -1, -4, -3, -12 = 1 \}$ & 6 \\
5 & $\Gr^{(4)} = \{ 5, 25 = -1, -5, 1 \}$ & 4 \\
6 & $\Gr = \{6, 36 = -3, -5, -4, 2, -1, -6, 3, 5, 4, -2, -12 = 1 \}$ & 12, ген. \\
7 = -6 & $\Gr = \{ -6, 36 = -3, 5, -4, -2, -1, 6, 3, -5, 4, 2, -12 = 1 \}$ & 12, ген. \\
8 = -5 & $\Gr^{(4)} = \{ -5, 25 = -1, 5, 1 \}$ & 4 \\
9 = -4 & $\Gr^{(3)} = \{ -4, 16 = 3, -12 = 1 \}$ & 3 \\
10 = -3 & $\Gr^{(6)} = \{ -3, 9 = -4, 12 = -1, 3, -9 = 4, -12 = 1 \}$ & 6 \\
11 = -2 & $\Gr = \{ -2, 4, 5, 3, -6, -1, 2, -4, -5, -3, 6, -12 = 1 \}$ & 12, ген. \\
12 = -1 & $\Gr^{(2)} = \{ -1, 1 \}$ & 2 \\
\hline
\end{tabular} }
\end{table}
\exampleend
\subsection{Группа $\Z_n^*$}
\textbf{Функция Эйлера}\index{функция!Эйлера} $\varphi(n)$ определяется как количество чисел, взаимно простых с $n$ , в интервале от 1 до $n-1$.
Если $n=p$ -- простое число, то
\[ \varphi(p) = p - 1, \]
\[ \varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1). \]
Если $n$ -- составное число и
\[ n = \prod \limits_{i} p_i^{k_i} \]
разложено на простые множители $p_i$, то
\[ \varphi(n) = \prod \limits_{i} \varphi(p_i^{k_i}) = \prod \limits_{i} p_i^{k_i - 1}(p_i - 1). \]
\textbf{Группой $\Z_n^*$} называется группа\index{группа!$\Z_n^*$}
\[ \Z_n^* = \left\{ \forall a \in \left\{ 1, 2, \dots, n-1 \mod n \right\} : \gcd(a,n) = 1 \right\}, \]
с операцией умножения $\ast$ по $\mod n$.
Порядок группы --
\[ |\Z_n^*| = \varphi(n). \]
Группа $\Z_p^*$ -- частный случай группы $\Z_n^*$.
Если $n$ \emph{составное} (не простое) число, то группа $\Z_n^*$ \textbf{нециклическая}.
Из того, что $\Z_n^*$ -- группа, для любых $a \neq 0, n > 1: \gcd(a,n) = 1$ следует \textbf{теорема Эйлера}\index{теорема!Эйлера}:
\[ a^{\varphi(n)} = 1 \mod n. \]
При возведении в степень, если $\gcd(a,n) = 1$, выполняется
\[ a^b = a^{b \mod \varphi(n)} \mod n. \]
\example
В табл. \ref{tab:Zn-sample} приведена нециклическая группа $\Z_{21}^*$ и ее циклические подгруппы
\[ \Gr^{(1)}, \Gr_1^{(2)}, \Gr_2^{(2)}, \Gr_3^{(2)}, \Gr_1^{(3)}, \Gr_1^{(6)}, \Gr_2^{(6)}, \Gr_3^{(6)}, \]
верхний индекс обозначает порядок подгруппы, нижний индекс нумерует различные подгруппы одного порядка.
\begin{table}[h!]
\centering
\caption{Циклические подгруппы нециклической группы $\Z_{21}^*$\label{tab:Zn-sample}}
\begin{tabular}{|c|l|c|}
\hline
Элемент & Порождаемая циклическая подгруппа & Порядок \\
\hline
1 & $\Gr^{(1)} = \{ 1 \}$ & 1 \\
2 & $\Gr_1^{(6)} = \{ 2, 4, 8, 16, 11, 1 \}$ & 6 \\
4 & $\Gr_1^{(3)} = \{ 4, 16, 1 \}$ & 3 \\
5 & $\Gr_2^{(6)} = \{ 5, 4, 20, 16, 17, 1 \}$ & 6 \\
8 & $\Gr_1^{(2)} = \{ 8, 1 \}$ & 2 \\
10 & $\Gr_3^{(6)} = \{ 10, 16, 13, 4, 19, 1 \}$ & 6 \\
11 & $\Gr_1^{(6)} = \{ 11, 16, 8, 4, 2, 1 \}$ & 6 \\
13 & $\Gr_2^{(2)} = \{ 13, 1 \}$ & 2 \\
16 & $\Gr_1^{(3)} = \{ 16, 4, 1 \}$ & 3 \\
17 & $\Gr_2^{(6)} = \{ 17, 16, 20, 4, 5, 1 \}$ & 6 \\
19 & $\Gr_3^{(6)} = \{ 19, 4, 13, 16, 10, 1 \}$ & 6 \\
20 & $\Gr_3^{(2)} = \{ 20, 1 \}$ & 2 \\
\hline
\end{tabular}
\end{table}
\exampleend