From bcee37a8dda3ced1c09a671ddf321352bbc284e9 Mon Sep 17 00:00:00 2001 From: Andrew Guschin 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/lab1/lab1.pdf | Bin 0 -> 131330 bytes reports/lab1/lab1.tex | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 115 insertions(+) create mode 100644 reports/lab1/lab1.pdf create mode 100644 reports/lab1/lab1.tex (limited to 'reports/lab1') diff --git a/reports/lab1/lab1.pdf b/reports/lab1/lab1.pdf new file mode 100644 index 0000000..f4f73f7 Binary files /dev/null and b/reports/lab1/lab1.pdf differ diff --git a/reports/lab1/lab1.tex b/reports/lab1/lab1.tex new file mode 100644 index 0000000..f7bd293 --- /dev/null +++ b/reports/lab1/lab1.tex @@ -0,0 +1,115 @@ +\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$ – бинарная операция, удовлетворяющая следующим трём аксиомам: + \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*} + +Полем называется алгебраическая структура $$, состоящая +из непустого множества и двух бинарных операция. Поле является группой +по сложению и группой по умножению (обратный элемент по умножению +рассматривается для ненулевых элементов), связанных аксиомами дистрибутивности $(\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} -- cgit v1.2.3