Добавлена вторая лекция по МАГК

5 files changed, 238 insertions, 0 deletions

diff --git a/crypto-algebra/crypto-algebra.pdf b/crypto-algebra/crypto-algebra.pdf
new file mode 100644
index 0000000..a8f0f3f
--- /dev/null
+++ b/crypto-algebra/crypto-algebra.pdf
diff --git a/crypto-algebra/crypto-algebra.tex b/crypto-algebra/crypto-algebra.tex
new file mode 100644
index 0000000..bc2c47a
--- /dev/null
+++ b/crypto-algebra/crypto-algebra.tex
@@ -0,0 +1,22 @@
+\documentclass{../Lecture}
+
+\usepackage{../preamble}
+\newtheorem{theorem}{Теорема}
+\newtheorem{statement}{Утверждение}
+
+\title{Методы алгебраической геометрии в криптографии}
+\author{Андрей Гущин}
+\date{\today}
+
+\begin{document}
+
+\maketitle
+\tableofcontents
+\thispagestyle{empty}
+\newpage
+
+% Семестр 1
+\input{lectures/lecture1.tex}
+\input{lectures/lecture2.tex}
+
+\end{document}
diff --git a/crypto-algebra/lectures/lecture1.tex b/crypto-algebra/lectures/lecture1.tex
new file mode 100644
index 0000000..befaab3
--- /dev/null
+++ b/crypto-algebra/lectures/lecture1.tex
@@ -0,0 +1,6 @@
+% Лекция 1 (04.09.23)
+
+\section*{Введение}
+
+
+
diff --git a/crypto-algebra/lectures/lecture2.tex b/crypto-algebra/lectures/lecture2.tex
new file mode 100644
index 0000000..c7f8f44
--- /dev/null
+++ b/crypto-algebra/lectures/lecture2.tex
@@ -0,0 +1,175 @@
+% Лекция 2 (11.09.23)
+
+Взяв из каждого класса по одному вычету, получим \emph{полную систему вычетов}.
+...
+
+Непустое подмножество $H$ группы $G$ называется \emph{подгруппой} этой группы,
+если $H$ образует группу относительно операции группы $G$.
+
+Группа $G$ называется \emph{циклической}, если существует элемент $\alpha \in
+G$ такой, что для каждого $b \in G$ существует целое число $i$ такое, что $b =
+\alpha^i$.
+
+Такой элемент $\alpha$ называется \emph{образующим элементом} группы $G$.
+
+\begin{theorem}[О циклической подгруппе] %% NOTE: 4
+  Если $G$ --- группа и $a \in G$, то множество всех степеней $a$ образует
+  циклическую подгруппу группы $G$, называемую подгруппой, порождённой $a$, и
+  обозначаемую через $\langle a \rangle$.
+\end{theorem}
+
+Пусть $G$ --- группа и $a \in G$. Порядок элемента $a$ определяется как
+наименьшее положительное число $t$ такое, что $a^t = 1$, при условии, что такое
+целое число существует.
+
+Если такого $t$ не существует, то порядок $a$ определяется как $\infty$ (элемент
+бесконечного порядка).
+
+\begin{theorem}[О порядке подгруппы] %% NOTE: 5
+  Пусть $G$ --- группа и $a \in G$ --- элемент конечного порядка $t$. Тогда
+  порядок подгруппы, порождённой $a$, равен $t: |\langle a \rangle| = t$.
+\end{theorem}
+
+\begin{theorem}[Лагранжа]
+  Если $G$ --- конечная группа и $H$ подгруппа $G$, то $|H|$ делит $|G|$.
+  Следовательно, если $a \in G$, то порядок $a$ делит $|G|$.
+\end{theorem}
+
+\begin{theorem}[О циклической группе]
+  Каждая подгруппа циклической группы $G$ также является циклической. На
+  самом деле, если $G$ --- циклическая группа порядка $n$, то для каждого
+  положительного делителя $d$ числа $n$ в $G$ содержится ровно одна подгруппа
+  порядка $d$.
+\end{theorem}
+
+\begin{theorem}[Порядок элемента и количество образующих]
+  Пусть $G$ --- группа.
+  \begin{enumerate}
+    \item
+      Если порядок $a \in G$ равен $t$, то порядок $a^k = \frac{t}{\gcd(t, k)}$,
+    \item
+      Если $G$ --- циклическая группа порядка $n$ и $d \mid n$, то в $G$ ровно
+      $\varphi(d)$ элементов порядка $d$. В частности, $G$ имеет $\varphi(n)$
+      образующих.
+  \end{enumerate}
+\end{theorem}
+
+Две группы $G$ и $G'$ с операциями $\cdot$ и $\circ$ называются \emph{изоморфными}
+($G \cong G'$), если существует отображение $f : G \to G'$, такое, что
+\begin{enumerate}
+  \item $(\forall a, b \in G) \quad f(a \cdot b) = f(a) \circ f(b)$;
+  \item $f$ --- биективно.
+\end{enumerate}
+
+\begin{theorem}[Об изоморфизме циклических групп]
+  Все циклические группы одного и того же порядка (в том числе и бесконечного)
+  изоморфны.
+\end{theorem}
+
+Положив $G' = G$ в определении изоморфизма, получается изоморфное
+отображение $\varphi : G \mapsto G$ группы $G$ на себя, которое называется
+\emph{автоморфизмом} группы $G$.
+
+Отображение $f : G \mapsto G'$ группы $(G, \cdot)$ в группу $(G', \circ)$
+называется \emph{гомоморфизмом}, если оно согласовано с операциями на группах
+$G$ и $G'$, то есть
+\begin{equation*}
+  (\forall a, b \in G) \quad f(a \cdot b) = f(a) \circ f(b)
+\end{equation*}
+
+Гомоморфизм вида $f : G \mapsto G$ называется эндоморфизмом. Абелева группа
+называется примарной, если порядок каждого её элемента есть степень одного и
+того же простого числа $p$.
+
+Всякая абелева группа, не содержащая элементов бесконечного порядка, разлагается
+в прямую сумму примарных групп.
+
+%% TODO: 3?
+3) \emph{Кольцо} $(R, +, \times)$ состоит из множества $R$ с двумя бинарными
+операциями, обозначаемыми $+$ (сложение) и $\times$ (умножение) на $R$,
+удовлетворяющими следующим аксиомам:
+\begin{enumerate}
+  \item
+    $(R, +)$ --- абелева группа с нейтральным элементом, обозначенным 0;
+  \item
+    Операция $\times$ ассоциативна, то есть \[ (\forall a, b, c \in R) \quad a
+    \times (b \times c) = (a \times b) \times c \]
+  \item
+    Операция $\times$ дистрибутивна над $+$, то есть \[ a \times (b + c) = (a
+    \times b) + (a \times c) \] и \[ (b + c) \times a = b \times a + c \times a
+    \] для всех $a, b, c \in R$.
+\end{enumerate}
+
+Кольцо называется \emph{кольцом с единицей}, если оно имеет мультипликативный
+нейтральный элемент, обозначаемый 1, где $1 \neq 0$, такой, что
+\begin{equation*}
+  (\forall a \in R) \quad 1 \times a = a \times 1 = a
+\end{equation*}
+
+Кольцо называется коммутативным, если
+\begin{equation*}
+  (\forall a, b \in R) \quad a \times b = b \times a
+\end{equation*}
+
+Элемента $a$ кольца $R$ называется \emph{обратимым элементом}, если существует
+элемент $b \in R$ такой, что $a \times b = 1$.
+
+%% TODO: 4
+4) \emph{Поля} --- это коммутативное кольцо с единицей, в котором все ненулевые
+элементы имеют мультипликативные обратные.
+
+\emph{Характеристика} поля равна 0, если сумма $\underbrace{1 + 1 + \dots +
+1}_{m \text{ раз}}$ не равна нулю для любого $m \geq 1$.
+
+В противном случае характеристикой поля является наименьшее натуральное число
+$m$ такое, что $\sum_{i = 1}^m 1 = 0$.
+
+\begin{theorem}[Поле $\Z_n$] %$ NOTE: 10
+  $\Z_n$ является полем (с обычными операциями сложения и умножения по модулю
+  $n$) $\iff$ $n$ --- простое число. Если $n$ --- простое, то $\Z_n$ имеет
+  характеристику $n$.
+\end{theorem}
+
+\begin{theorem}[О характеристике поля]
+  Если характеристика $m$ поля отлична от 0, то $m$ --- простое число.
+\end{theorem}
+
+Подмножество $F$ поля $K$ является \emph{подполем} $K$, если $F$ само является
+полем по отношению к операциям $K$. В этом случае говорят, что $K$ является
+\emph{расширением} поля $F$.
+
+Определим квадратичный характер $\chi$ поля $K$:
+\begin{equation*}
+  \begin{cases} %% TODO: выражения
+    \chi(a) = 1, &\text{если a --- квадратичный вычет в поле K} \\
+    \chi(a) = -1, &\text{если a --- квадратичный невычет в поле K} \\
+    \chi(0) = 0 &
+  \end{cases}
+\end{equation*}
+
+
+5) Если $R$ --- коммутативное кольцо с единицей, то \emph{полином} от
+неопределённого $x$ над кольцом $R$ --- это выражение вида
+\begin{equation*}
+  f(x) = a_n x^n + \dots + a_2 x^2 + a_1 x + a_0
+\end{equation*}
+где каждое $a_i \in R$ и $n \geq 0$. Элемент $a_i$ называется
+\emph{коэффициентом} при $x_i$ в $f(x)$.
+
+Если $R$ --- коммутативное кольцо с единицей, кольцо полиномов $R[x]$ --- это
+кольцо, образованное множеством всех полиномов от неопределённого $x$, имеющих
+коэффициенты из $R$.
+
+Две операции --- это стандартное полиномиальное сложение и умножение с
+арифметикой коэффициентов, выполняемой в кольце $R$.
+
+Элемент $\alpha \in R$ есть корень полинома $f(x) \in R[x] \iff (x - \alpha)
+\mid f(x)$.
+
+\emph{Кратностью корня} $\alpha \in R$ полинома $f(x) \in R[x]$ называют число
+$k \in \N$ со свойствами
+\begin{equation*}
+  (x - \alpha)^k \mid f(x),\, (x - \alpha)^{k + 1} \nmid f(x),
+\end{equation*}
+и говорят, что $\alpha$ --- \emph{простой корень} $f(x)$, если $k = 1$, и
+$\alpha$ --- \emph{кратный корень} $f(x)$, если $k > 1$.
diff --git a/crypto-algebra/maker.sh b/crypto-algebra/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/crypto-algebra/maker.sh
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+watch() {
+    [ -z "$1" ] && echo "Необходимо указать название основного документа" && help
+    set -o xtrace
+    latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1
+}
+
+doc() {
+    [ -z "$1" ] && echo "Необходимо указать название основного документа" && help
+    set -o xtrace
+    latexmk -pdf -f -shell-escape -interaction=nonstopmode $1
+}
+
+clean() {
+    set -o xtrace
+    rm -rf _minted-*
+    find . -name "*.aux" -exec rm {} \;
+    rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc
+}
+
+help() {
+    echo "Использование:"
+    echo "./maker.sh watch <main-doc>.tex -> Запуск процесса, пересобирающего документ при изменениях"
+    echo "./maker.sh doc <main-doc>.tex -> Пересобрать документ"
+    echo "./maker.sh clean -> Удаление сгенерированных файлов"
+    exit 1
+}
+
+case "$1" in
+    watch) watch $2 ;;
+    doc) doc $2 ;;
+    clean) clean ;;
+    *) help ;;
+esac