From bcee37a8dda3ced1c09a671ddf321352bbc284e9 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sun, 13 Nov 2022 11:43:52 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?=
 =?UTF-8?q?=20=D0=BE=D1=82=D1=87=D1=91=D1=82=D1=8B=20=D0=BF=D0=BE=201,=203?=
 =?UTF-8?q?,=204,=206=20=D0=B8=207=20=D0=BB=D0=B0=D0=B1=D0=B0=D0=BC?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 reports/lab6/lab6.tex | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 143 insertions(+)
 create mode 100644 reports/lab6/lab6.tex

(limited to 'reports/lab6/lab6.tex')

diff --git a/reports/lab6/lab6.tex b/reports/lab6/lab6.tex
new file mode 100644
index 0000000..9e0c78c
--- /dev/null
+++ b/reports/lab6/lab6.tex
@@ -0,0 +1,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}
-- 
cgit v1.2.3

