From 1b17ea5691dc3921da664cdf898786352cd10f24 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Tue, 12 Sep 2023 13:56:49 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?= =?UTF-8?q?=20=D0=B2=D1=82=D0=BE=D1=80=D0=B0=D1=8F=20=D0=BB=D0=B5=D0=BA?= =?UTF-8?q?=D1=86=D0=B8=D1=8F=20=D0=BF=D0=BE=20=D0=9C=D0=90=D0=93=D0=9A?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- crypto-algebra/crypto-algebra.pdf | Bin 0 -> 205623 bytes crypto-algebra/crypto-algebra.tex | 22 +++++ crypto-algebra/lectures/lecture1.tex | 6 ++ crypto-algebra/lectures/lecture2.tex | 175 +++++++++++++++++++++++++++++++++++ crypto-algebra/maker.sh | 35 +++++++ 5 files changed, 238 insertions(+) create mode 100644 crypto-algebra/crypto-algebra.pdf create mode 100644 crypto-algebra/crypto-algebra.tex create mode 100644 crypto-algebra/lectures/lecture1.tex create mode 100644 crypto-algebra/lectures/lecture2.tex create mode 100755 crypto-algebra/maker.sh (limited to 'crypto-algebra') diff --git a/crypto-algebra/crypto-algebra.pdf b/crypto-algebra/crypto-algebra.pdf new file mode 100644 index 0000000..a8f0f3f Binary files /dev/null and b/crypto-algebra/crypto-algebra.pdf differ 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 .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac -- cgit v1.2.3