\documentclass[a4paper,oneside]{article}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}

\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{amsthm}

\newtheorem{theorem}{Теорема}[subsection]
\newtheorem*{theorem*}{Теорема}

% --- Определение --- %
\theoremstyle{definition}
\newtheorem{definition}{Определение}[subsection]
\newtheorem*{definition*}{Определение}
% ------------------- %

\date{}


\title{Криптографические методы защиты информации, Лабораторная работа №1}
\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}

\begin{document}

\maketitle

\begin{definition*}
    Группой называется пара $<G, \cdot>$, где $G$ – непустое множество, а
    $\cdot$ – бинарная операция, удовлетворяющая следующим трём аксиомам:
    \begin{enumerate}
        \item Ассоциативность
        \item Существование единичного (нейтрального) элемента
        \item Существование обратного элемента
    \end{enumerate}
\end{definition*}

Поле является алгебраической структурой с двумя бинарными операциями
– операцией сложения и операцией умножения. Поскольку, для элементов
поля по каждой из этих операций существует обратный элемент, то в поле
определены 4 арифметических операции – сложение, вычитание, умножение
и деление.

Простейшее поле состоит ровно из p элементов, где $p$-произвольное простое
число, включая $p = 2$:
\begin{equation*}
    F_p = \{ 0, 1, 2, \dots, p - 1 \}
\end{equation*}

Полем называется алгебраическая структура $<F, +, \cdot>$, состоящая
из непустого множества и двух бинарных операция. Поле является группой
по сложению и группой по умножению (обратный элемент по умножению
рассматривается для ненулевых элементов), связанных аксиомами дистрибутивности $(\forall a, b, c \in F)$.

*Определение*. Порядком элемента $a$ группы $G$ (обозначается
$ord_G(a)$) называется наименьшее число $k$ такое, что $a^k =
1$. Порядком группы называется число ее элементов.

Порядком (по умножению) ненулевого элемента $a$ поля $F_p$ называется
наименьшая степень $t$ такая, что выполняется условие
\begin{equation*}
    a^t \pmod p = 1
\end{equation*}

\begin{theorem*}[Лагранжа]
    Порядок любого элемента конечной группы является делителем порядка
    группы.
\end{theorem*}

Элемент $a \in G$ называется \textit{примитивным} элементом или
генератором группы, если его порядок $ord_G(a)$ равен порядку
группы. Не любая группа имеет генератор. Группа, в которой есть
генератор, порождается одним элементом и называется циклической.

Проверим, что 2 является порождающим элементом простого конечного поля
$F_{29}$
\begin{align*}
    2^{1} &= 2 \pmod {29} = 2 \\
    2^{2} &= 2 \cdot 2 \pmod {29} = 4 \\
    2^{3} &= 4 \cdot 2 \pmod {29} = 8 \\
    2^{4} &= 8 \cdot 2 \pmod {29} = 16 \\
    2^{5} &= 16 \cdot 2 \pmod {29} = 3 \\
    2^{6} &= 3 \cdot 2 \pmod {29} = 6 \\
    2^{7} &= 6 \cdot 2 \pmod {29} = 12 \\
    2^{8} &= 12 \cdot 2 \pmod {29} = 24 \\
    2^{9} &= 24 \cdot 2 \pmod {29} = 19 \\
    2^{10} &= 19 \cdot 2 \pmod {29} = 9 \\
    2^{11} &= 9 \cdot 2 \pmod {29} = 18 \\
    2^{12} &= 18 \cdot 2 \pmod {29} = 7 \\
    2^{13} &= 7 \cdot 2 \pmod {29} = 14 \\
    2^{14} &= 14 \cdot 2 \pmod {29} = 28 \\
    2^{15} &= 28 \cdot 2 \pmod {29} = 27 \\
    2^{16} &= 27 \cdot 2 \pmod {29} = 25 \\
    2^{17} &= 25 \cdot 2 \pmod {29} = 21 \\
    2^{18} &= 21 \cdot 2 \pmod {29} = 13 \\
    2^{19} &= 13 \cdot 2 \pmod {29} = 26 \\
    2^{20} &= 26 \cdot 2 \pmod {29} = 23 \\
    2^{21} &= 23 \cdot 2 \pmod {29} = 17 \\
    2^{22} &= 17 \cdot 2 \pmod {29} = 5 \\
    2^{23} &= 5 \cdot 2 \pmod {29} = 10 \\
    2^{24} &= 10 \cdot 2 \pmod {29} = 20 \\
    2^{25} &= 20 \cdot 2 \pmod {29} = 11 \\
    2^{26} &= 11 \cdot 2 \pmod {29} = 22 \\
    2^{27} &= 22 \cdot 2 \pmod {29} = 15 \\
    2^{28} &= 15 \cdot 2 \pmod {29} = 1
\end{align*}

Порядок элемента 2 в поле $F_{29}$ равно 28 (то есть $p - 1$), таким
образом число 2 является порождающим элементом конечного поля
$F_{29}$.
\end{document}