groups.texe

\section{Группы}\label{section-groups}
\selectlanguage{russian}

\subsection{Свойства групп}

\emph{Группой}\index{группа} называется множество $\Gr$, на котором задана бинарная операция <<$\circ$>>, удовлетворяющая следующим аксиомам:
\begin{enumerate}
    \item замкнутость:
        \[ \forall a,b \in \Gr: a \circ b = c \in \Gr; \]
    \item ассоциативность:
        \[ \forall a,b,c \in \Gr: (a \circ b) \circ c = a \circ (b \circ c); \]
    \item существование единичного элемента:
        \[ \exists ~ e \in \Gr: e\circ a = a \circ e = a; \]
    \item существование обратного элемента:
        \[ \forall a \in \Gr ~ \exists ~ b \in \Gr: a \circ b = b \circ a = e. \]
\end{enumerate}
Если
    \[ \forall a,b \in \Gr: a \circ b = b \circ a, \]
то такую группу называют \emph{коммутативной} (или \emph{абелевой}).

Если операция в группе задана как умножение <<$\cdot$>>, то группа называется \emph{мультипликативной}, Для мультипликативной группы будем использовать следующие соглашения об обозначениях:
\begin{itemize}
	\item нейтральный элемент: $e \equiv 1$;
	\item обратный элемент: $a^{-1}$;
	\item повторение операции над одним аргументом $k$ раз (возведение в степень k): $a^k$.
\end{itemize}

Если операция задана как сложение <<$+$>>, то группа называется \emph{аддитивной}. Соглашение об обозначениях для аддитивной группы:
\begin{itemize}
	\item нейтральный элемент: $e \equiv 0$;
	\item обратный элемент: $-a$;
	\item повторение операции над одним аргументом $k$ раз (умножение на k): $ka$.
\end{itemize}

Подмножество группы, удовлетворяющее аксиомам группы, называется \emph{подгруппой}\index{подгруппа}.

\emph{Порядком} $|\Gr|$ \emph{группы}\index{порядок группы} $\Gr$ называется число элементов в группе. Пусть группа мультипликативная. Для любого элемента $a \in \Gr$ выполняется $a^{|\Gr|} = 1$.

\emph{Порядком элемента} $a$ называется минимальное натуральное число
    \[ \ord(a): a^{\ord(a)} = 1. \]

 Порядок элемента, согласно теореме Лагранжа\index{теорема!Лагранжа}, делит порядок группы:
    \[ \ord(a) \mid \left|\Gr\right|. \]


\subsection{Циклические группы}

\emph{Генератором} $g \in \Gr$ называется элемент, \emph{порождающий} всю группу\index{генератор группы}:
    \[ \Gr = \{g, g^2, g^3, \ldots, g^{|\Gr|} = 1\}. \]

Группа, в которой существует генератор, называется \emph{циклической}\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}

Из предыдущего утверждения следует, что число генераторов в циклической группе равно
    \[ \varphi(|\Gr|). \]

Для проверки, является ли элемент генератором всей группы, требуется знать разложение порядка группы $|\Gr|$ на множители. Далее элемент возводится в степени, равные всем делителям порядка группы, и сравнивается с единичным элементом $e$. Если ни одна из степеней не равна $e$, то этот элемент является примитивным элементом или генератором группы. В противном случае элемент будет генератором какой-либо подгруппы.

Задача разложения числа на множители является трудной для вычисления. На сложности её решения, например, основана криптосистема RSA\index{криптосистема!RSA}. Поэтому при создании больших групп желательно заранее знать разложение порядка группы на множители для возможности выбора генератора.


\subsection{Группа $\Z_p^*$}\label{section-group-multiplicative}

\emph{Группой $\Z_p^*$} называется группа\index{группа!$\Z_p^*$}
    \[ \Z_p^* = \{1, 2, \dots, p-1 \mod p\}, \]
где $p$ -- простое\index{число!простое} число, операция в группе -- умножение $\ast$ по $\Mod p$.

Группа $\Z_p^*$ -- \emph{циклическая}, порядок
    \[ |\Z_p^*| = \varphi(p) = p - 1. \]
Число генераторов в группе --
    \[ \varphi(|\Z_p^*|) = \varphi(p-1). \]

Из того, что $\Z_p^*$ -- группа, для простого\index{число!простое} $p$ и любого $a \in [2, p-1] \mod p$ следует \emph{малая теорема Ферма}\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}[!ht]
    \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, 3, 6, 12, 11, 9, 5, 10, 7, 1 \}$ & 12, ген. \\
         3 & $\Gr^{(3)} = \{ 3, 9, 1 \}$ & 3 \\
         4 & $\Gr^{(6)} = \{ 4, 3, 12, 9, 10, 1 \}$ & 6 \\
         5 & $\Gr^{(4)} = \{ 5, 12, 8, 1 \}$ & 4 \\
         6 & $\Gr = \{ 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1 \}$ & 12, ген. \\
         7 & $\Gr = \{ 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1 \}$ & 12, ген. \\
         8 & $\Gr^{(4)} = \{ 8, 12, 5, 1 \}$ & 4 \\
         9 & $\Gr^{(3)} = \{ 9, 3, 1 \}$ & 3 \\
        10 & $\Gr^{(6)} = \{ 10, 9, 12, 3, 4, 1 \}$ & 6 \\
        11 & $\Gr = \{ 11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1 \}$ & 12, ген. \\
        12 & $\Gr^{(2)} = \{ 12, 1 \}$ & 2 \\
        \hline
    \end{tabular} }
\end{table}
\exampleend


\subsection{Группа $\Z_n^*$}

\emph{Функция Эйлера}\index{функция!Эйлера} $\varphi(n)$ определяется как количество чисел, взаимно простых с $n$ в интервале от 1 до $n-1$.

Если $n=p$ -- простое\index{число!простое} число, то
    \[ \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). \]

\emph{Группой $\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{составное}\index{число!составное} (не простое) число, то группа $\Z_n^*$ \emph{нециклическая}.

Из того, что $\Z_n^*$ -- группа, для любых $a \neq 0, n > 1: \gcd(a,n) = 1$ следует \emph{теорема Эйлера}\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}[!ht]
    \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

\subsection{Конечные поля}\label{section-fields}

\emph{Полем} называется множество $\F$, для которого\index{поле}:
\begin{itemize}
    \item заданы две бинарные операции, условно называемые операциями умножения <<$\cdot$>> и сложения <<$+$>>;
    \item выполняются аксиомы группы для операции <<сложения>>: \\
        1. замкнутость:
		\[\forall a, b \in \F: a + b \in \F;\]
        2. ассоциативность:
		\[\forall a, b, c \in \F: (a+b)+c = a+(b+c);\]
        3. существование нейтрального элемента по сложению (часто обозначаемого как <<0>>):
		\[\exists 0 \in \F: \forall a \in \F: a + 0 = 0 + a = a; \]
        4. существование обратного элемента:
		\[\forall a \in \F: \exists -a: a + (-a) = 0; \]
    \item выполняются аксиомы группы для операции <<умножения>>, за одним исключением: \\
        1. замкнутость:
		\[\forall a, b \in \F: a \cdot b \in \F; \]
        2. ассоциативность:
		\[\forall a, b, c \in \F: (a \cdot b) \cdot c = a \cdot (b \cdot c);\]
        3. существование нейтрального элемента по умножению (часто обозначаемого как <<1>>):
		\[\exists 1 \in \F: \forall a \in \F: a \cdot 1 = 1 \cdot a = a;\]
        4. существование обратного элемента по умножению для всех элементов множества, кроме нейтрального элемента по сложению:
		\[\forall a \in {\F \setminus \{0\}}: \exists a^{-1}: a \cdot a^{-1} = a^{-1} \cdot a = 1;\]
    \item операции <<сложения>> и <<умножения>> коммутативны: \\
        \[ \begin{array}{l}
            \forall a, b \in \F: a + b = b + a, \\
            \forall a, b \in \F: a \cdot b = b \cdot a; \\
        \end{array} \]
    \item выполняется свойство дистрибутивности:
        \[ \forall a, b, c \in \F: a \cdot (b + c) = (a \cdot b) + (a \cdot c). \]
\end{itemize}

Примеры \emph{бесконечных} полей (с бесконечным числом элементов): поле рациональных чисел $\group{Q}$, поле вещественных чисел $\group{R}$, поле комплексных чисел $\group{C}$ с обычными операциями сложения и умножения.

В криптографии рассматриваются \emph{конечные} поля (с конечным числом элементов), называемые также \emph{полями Галуа}.

Число элементов в любом конечном поле равно $p^n$, где $p$ -- простое\index{число!простое} число и $n$ -- натуральное число. Обозначения поля Галуа: $\GF{p}, \GF{p^n}, \F_p, \F_{p^n}$ (аббревиатура от \langen{Galois field}). Все поля Галуа $\GF{p^n}$ изоморфны друг другу (существует взаимно однозначное отображение между полями, сохраняющее действие всех операций). Другими словами, существует только одно поле Галуа $\GF{p^n}$ для фиксированных $p, n$.

Приведём примеры конечных полей.

Двоичное поле $\GF{2}$ состоит из двух элементов. Однако задать его можно разными способами:
\begin{itemize}
	\item Как множество из двух чисел <<0>> и <<1>> с определёнными на нём операциями <<сложение>> и <<умножение>> как сложение и умножение чисел по модулю 2. Нейтральным элементом по сложению будет <<0>>, по умножению -- <<1>>:
\[\begin{array}{ll}
	0 + 0 = 0,	& 	0 \cdot 0 = 0, \\
	0 + 1 = 1,	& 	0 \cdot 1 = 0, \\
	1 + 0 = 1,	& 	1 \cdot 0 = 0, \\
	1 + 1 = 0,	& 	1 \cdot 1 = 1. \\
\end{array}\]
	\item Как множество из двух логических объектов <<ЛОЖЬ>> ($F$) и <<ИСТИНА>> ($T$) с определёнными на нём операциями <<сложение>> и <<умножение>> как булевые операции <<исключающее или>> и <<и>> соответственно. Нейтральным элементом по сложению будет <<ЛОЖЬ>>, по умножению -- <<ИСТИНА>>:
\[\begin{array}{ll}
	F + F = F,	& 	F \cdot F = F, \\
	F + T = T,	& 	F \cdot T = F, \\
	T + F = T,	& 	T \cdot F = F, \\
	T + T = F,	& 	T \cdot T = T. \\
\end{array}\]
	\item Как множество из двух логических объектов <<ЛОЖЬ>> ($F$) и <<ИСТИНА>> ($T$) с определёнными на нём операциями <<сложение>> и <<умножение>> как булевые операции <<эквивалентность>> и <<или>> соответственно. Нейтральным элементом по сложению будет <<ИСТИНА>>, по умножению -- <<ЛОЖЬ>>:
\[\begin{array}{ll}
	F + F = T,	& 	F \cdot F = F, \\
	F + T = F,	& 	F \cdot T = T, \\
	T + F = F,	& 	T \cdot F = T, \\
	T + T = T,	& 	T \cdot T = T. \\
\end{array}\]
	\item Как множество из двух чисел <<0>> и <<1>> с определёнными на нём операциями <<сложение>> и <<умножение>>, заданными в табличном представлении. Нейтральным элементом по сложению будет <<1>>, по умножению -- <<0>>:
\[\begin{array}{ll}
	0 + 0 = 1,	& 	0 \cdot 0 = 0, \\
	0 + 1 = 0,	& 	0 \cdot 1 = 1, \\
	1 + 0 = 0,	& 	1 \cdot 0 = 1, \\
	1 + 1 = 1,	& 	1 \cdot 1 = 1. \\
\end{array}\]
\end{itemize}

Все перечисленные выше варианты множеств изоморфны друг другу. Поэтому в дальнейшем под конечным полем $\GF{p}$, где $p$ -- простое\index{число!простое} число, будем понимать поле, заданное как множество целых чисел от $0$ до $p-1$ включительно, на котором операции <<сложение>> и <<умножение>> заданы как операции сложения и умножения чисел по модулю числа $p$. Например, поле $\GF{7}$ будем считать состоящим из 7-ми чисел $\{0, 1, 2, 3, 4, 5, 6\}$ с операциями умножения $(\cdot \mod 7)$ и сложения $(+ \mod 7)$ по модулю.

Конечное поле $\GF{p^n}, n > 1$ строится \emph{расширением} \emph{базового} поля $\GF{p}$. Элемент поля представляется как многочлен степени $n-1$ (или меньше) с коэффициентами из базового поля $\GF{p}$:
    \[ \alpha = \sum\limits_{i=0}^{n-1} a_i x^i, ~ a_i \in \GF{p}. \]

Операция сложения элементов в таком поле традиционно задаётся как операция сложения коэффициентов при одинаковых степенях в базовом поле $\GF{p}$. Операция умножения -- как умножение многочленов со сложением и умножением коэффициентов в базовом поле $\GF{p}$ и дальнейшим приведением результата по модулю некоторого заданного (для поля) неприводимого\footnote{Многочлен называется \emph{неприводимым}\index{многочлен!неприводимый}, если он не раскладывается на множители, и \emph{приводимым}\index{многочлен!приводимый}, если раскладывается.} многочлена $m(x)$. Количество элементов в поле равно $p^n$.

Многочлен $g(x)$ называется \emph{примитивным элементом}\index{многочлен!примитивный} (генератором) поля, если его степени порождают все ненулевые элементы, то есть $\GF{p^n} \setminus \{0\}$, заданное неприводимым многочленом $m(x)$, за исключением нуля:
    \[ \GF{p^n} \setminus \{0\} = \{ g(x), g^2(x), g^3(x), \dots, g^{p^n-1}(x) = 1 \mod m(x) \}. \]

\example
В таблице~\ref{tab:irreducible-gf2} приведены примеры многочленов \emph{над полем} $\GF{2}$.
\begin{table}[!ht]
    \centering
    \caption{Пример многочленов над полем $\GF{2}$\label{tab:irreducible-gf2}}
    \begin{tabular}{|c|c|c|}
        \hline
        Многочлен & \parbox[c][1cm][c]{2.5cm}{\centering Упрощённая запись} & Разложение \\
        \hline
        \rule{0pt}{2.5ex}$'1' x + '0'$ & $x$ & неприводимый \\
        $'1' x + '1'$ & $x+1$ & неприводимый \\
        $'1' x^2 + '0' x + '0'$ & $x^2$ & $x \cdot x$ \\
        $'1' x^2 + '0'x + '1'$ & $x^2 + 1$ & $(x+1) \cdot (x+1)$ \\
        $'1' x^2 + '1' x + '0'$ & $x^2 + x$ & $x \cdot (x+1)$ \\
        $'1' x^2 + '1' x + '1'$ & $x^2 + x + 1$ & неприводимый \\
        $'1' x^3 + '0' x^2 + '0' x + '1'$ & $x^3 + 1$ & $(x+1) \cdot (x^2+x+1)$ \\
        \hline
    \end{tabular}
\end{table}
\exampleend