1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
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>$, где $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}
|
