diff options
Diffstat (limited to 'reports/lab6/lab6.tex')
| -rw-r--r-- | reports/lab6/lab6.tex | 143 |
1 files changed, 143 insertions, 0 deletions
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} |