Добавлены лабы 8-15HEADmaster

34 files changed, 988 insertions, 1 deletions

diff --git a/report/lab1/images/test.png b/report/lab1/images/test.png
new file mode 100644
index 0000000..3425735
--- /dev/null
+++ b/report/lab1/images/test.png
diff --git a/report/lab1/lab1.pdf b/report/lab1/lab1.pdf
new file mode 100644
index 0000000..ce1df61
--- /dev/null
+++ b/report/lab1/lab1.pdf
diff --git a/report/lab1/lab1.tex b/report/lab1/lab1.tex
new file mode 100644
index 0000000..4b26359
--- /dev/null
+++ b/report/lab1/lab1.tex
@@ -0,0 +1,90 @@
+\documentclass[a4paper,oneside]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+
+\usepackage{amsmath}
+\usepackage{indentfirst}
+\usepackage{mathtools}
+\usepackage{amsfonts}
+\usepackage{enumitem}
+\usepackage{amsthm}
+\usepackage{minted}
+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
+\usepackage{float}
+
+\newtheorem{theorem}{Теорема}[subsection]
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}[subsection]
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №1}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section{Задача}
+
+Решите сравнение вида $ax \equiv b \pmod{m}$ с помощью алгоритма Евклида.
+
+\section{Алгоритм}
+
+Алгоритм Евклида, вычисляющий наибольший общий делитель двух чисел, можно расширить
+для нахождения по заданным числам $a$ и $b$ таких целых $x$ и $y$, что
+$ax + by = d$, где $d$ --- $\gcd(a, b)$.
+
+Пусть для положительных целых чисел $a$ и $b$ $(a > b)$ известны $d = \gcd(a, b)
+= \gcd(b, a \pmod{b})$, а также числа $x'$ и $y'$, для которых $d = x'b + y'(a
+\pmod{b})$. Тогда значения $x$ и $y$, являющиеся решениями уравнения $ax + by =
+d$, находятся из соотношений
+\begin{equation*}
+    x = y', y = x' - y' \frac{a}{b}
+\end{equation*}
+
+Линейным сравнением называется уравнение вида $ax \equiv b \pmod{m}$. Оно имеет
+решение тогда и только тогда, когда $b$ делится на $d = \gcd(a, m)$. Если $d >
+1$, то уравнение можно упростить, заменив его на $a'x \equiv b' \pmod{m'}$),
+где $a' = a / d$, $b' = b / d$, $m' = m / d$. После такого преобразования числа
+$a'$ и $m'$ являются взаимно простыми.
+
+Алгоритм решения уравнения $a'x \equiv b' \pmod{m'}$) со взаимно простыми $a'$ и
+$m'$ состоит из двух частей:
+\begin{enumerate}
+  \item
+    Решаем уравнение $a'x = 1 \pmod{m'}$). Для этого при помощи расширенного
+    алгоритма Евклида ищем решение $(x_0, y_0)$ уравнения $a'x + m'y = 1$. Взяв
+    по модулю $m'$ последнее равенство, получим $a'x_0 = 1 \pmod{m'}$).
+  \item
+    Умножим на $b'$ равенство $a'x_0 = 1 \pmod{m'}$). Получим $a'(b'x_0) = b'
+    \pmod{m'}$), откуда решением исходного уравнения $a'x = b' \pmod{m'}$) будет
+    $x = b'x_0 \pmod{m'}$).
+\end{enumerate}
+
+Все решения сравнения находят по формуле $x_i = x + m'i$, где $i = 0, \dots, d -
+1$.
+
+\section{Реализация}
+
+Для реализации программы использовался язык программирования Rust с системой
+сборки cargo.
+
+\inputminted{rust}{../../lab1/src/main.rs}
+
+\section{Тестирование}
+
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=\textwidth]{test.png}
+\end{figure}
+
+\end{document}
diff --git a/report/lab1/lab1.xdv b/report/lab1/lab1.xdv
new file mode 100644
index 0000000..9748eb8
--- /dev/null
+++ b/report/lab1/lab1.xdv
diff --git a/report/lab1/maker.sh b/report/lab1/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab1/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
diff --git a/report/lab10/images/test10.png b/report/lab10/images/test10.png
new file mode 100644
index 0000000..67dfc55
--- /dev/null
+++ b/report/lab10/images/test10.png
diff --git a/report/lab10/lab10.pdf b/report/lab10/lab10.pdf
new file mode 100644
index 0000000..50eed16
--- /dev/null
+++ b/report/lab10/lab10.pdf
diff --git a/report/lab10/lab10.tex b/report/lab10/lab10.tex
new file mode 100644
index 0000000..2612ecc
--- /dev/null
+++ b/report/lab10/lab10.tex
@@ -0,0 +1,81 @@
+\documentclass[a4paper,oneside]{article}

+

+\usepackage[utf8]{inputenc}

+\usepackage[T2A]{fontenc}

+\usepackage[english,russian]{babel}

+

+\usepackage{amsmath}

+\usepackage{mathtools}

+\usepackage{amsfonts}

+\usepackage{enumitem}

+\usepackage{amsthm}

+\usepackage{minted}

+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}

+\usepackage{graphicx}

+\graphicspath{ {./images/} }

+\usepackage{float}

+

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

+\newtheorem*{theorem*}{Теорема}

+

+% --- Определение --- %

+\theoremstyle{definition}

+\newtheorem{definition}{Определение}[subsection]

+\newtheorem*{definition*}{Определение}

+% ------------------- %

+

+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №10}}

+\author{Гущин Андрей, 431 группа, 1 подгруппа}

+\date{\the\year{} г.}

+

+\begin{document}

+

+\maketitle

+

+\section{Задание}

+Осуществить построение большого простого числа с

+использованием теоремы Поклингтона.

+

+

+\section{Алгоритм}

+Критерий Поклингтона — детерминированный тест на простоту, разработанный

+Генри Поклингтоном и Дерриком Генри Лехмером. Критерий Поклингтона

+позволяет определять, является ли данное число простым.

+

+Пусть $n$ — натуральное число. Пусть число $n-1$ имеет простой делитель

+$q$, причем ${\displaystyle q>{\sqrt {n}}-1}$. Если найдётся такое целое

+число $a$, что выполняются следующие два условия:

+

+\begin{enumerate}

+    \item $a^{n-1} \equiv 1 \pmod n$

+    \item числа $n$ и $a^{(n-1)/q}-1$ взаимнопросты

+\end{enumerate}

+

+тогда $n$ - простое число.

+

+Практическая реализация основана на выборе случайного числа в

+диапазоне значений от $2^{b - 1} + 1$ до $2^b - 1$ (где $b$ определяет

+число бит генерируемого простого числа). Далее это число проверяется на

+наличие небольших простых делителей (простые числа меньше 500), и если

+таких делителей не найдено, осуществляется проверка с помощью теоремы

+Поклингтона. Для этого перед запуском программы вводится значение

+верхнего порога $a$, определяющее, что в рамках проверки на простоту с

+помощью теоремы Поклингтона будут использоваться целые числа, значение

+которых не превосходит $a$. Если число проходит тест, значит оно

+является сгенерированным простым числом. Если же число не проходит тест

+или у него есть делители среди небольших первых простых чисел, то выбирается

+другое число из этого диапазона, пока выбранное число не будет проходить

+тест успешно. 

+

+

+\section{Реализация}

+\inputminted{python}{../../lab10/lab10.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test10.png}

+\end{figure}

+

+\end{document}

diff --git a/report/lab10/maker.sh b/report/lab10/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab10/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
diff --git a/report/lab11/images/test11.png b/report/lab11/images/test11.png
new file mode 100644
index 0000000..ed4a42f
--- /dev/null
+++ b/report/lab11/images/test11.png
diff --git a/report/lab11/lab11.pdf b/report/lab11/lab11.pdf
new file mode 100644
index 0000000..c4669a0
--- /dev/null
+++ b/report/lab11/lab11.pdf
diff --git a/report/lab11/lab11.tex b/report/lab11/lab11.tex
new file mode 100644
index 0000000..9f74180
--- /dev/null
+++ b/report/lab11/lab11.tex
@@ -0,0 +1,80 @@
+\documentclass[a4paper,oneside]{article}

+

+\usepackage[utf8]{inputenc}

+\usepackage[T2A]{fontenc}

+\usepackage[english,russian]{babel}

+

+\usepackage{amsmath}

+\usepackage{mathtools}

+\usepackage{amsfonts}

+\usepackage{enumitem}

+\usepackage{amsthm}

+\usepackage{minted}

+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}

+\usepackage{graphicx}

+\graphicspath{ {./images/} }

+\usepackage{float}

+

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

+\newtheorem*{theorem*}{Теорема}

+

+% --- Определение --- %

+\theoremstyle{definition}

+\newtheorem{definition}{Определение}[subsection]

+\newtheorem*{definition*}{Определение}

+% ------------------- %

+

+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №11}}

+\author{Гущин Андрей, 431 группа, 1 подгруппа}

+\date{\the\year{} г.}

+

+\begin{document}

+

+\maketitle

+

+\section{Задача}

+Реализовать факторизацию Ферма.

+

+\section{Алгоритм}

+Ферма описал свой метод разложения больших чисел на множители. Он

+представлял собой первое реальное улучшение по сравнению с

+классическим методом попытки найти множитель $n$ путем деления на

+все простые числа, не превосходящие $\sqrt{n}$. В основе схемы

+факторизации Ферма лежит наблюдение, что поиск множителей нечетного

+целого числа $n$ (поскольку степени двойки легко распознаются и

+могут быть удалены в самом начале, нет никаких потерь в

+предположении, что $n$ нечетно) эквивалентен получению интегральных

+решений $x$ и $y$ уравнения $n = x^{2} - y^{2}$.

+

+Если $n$ --- разность двух квадратов, то очевидно, что $n$ можно разложить на

+множители как $n = x^{2}-y^{2} = (x+y)(x-y)$. И наоборот, когда $n$ имеет

+разложение $n = ab$, где $a \geq b \geq 1$, тогда мы можем записать $n =

+(\frac{a+b}{2})^{2}-(\frac{a-b}{2})^{2}$.

+

+Более того, поскольку $n$ считается нечетным целым числом, $a$ и $b$

+сами по себе нечетны и, следовательно, $\frac{a+b}{2}$ и

+$\frac{a-b}{2}$ будут целыми неотрицательными числами.

+

+Поиск возможных $x$ и $y$, удовлетворяющих уравнению $n=x^{2}-y^{2}$ или, что то

+же самое, уравнению $x^{2}-n=y^{2}$, начинают с определения наименьшее целое

+число $k$, для которого $k^{2} \geq n$. Рассмотрим последовательно числа

+$k^{2}-n$, $(k+1)^{2}-n$, $(k+2)^{2}-n$, $(k+3)^{2}-n$, $\ldots$, пока не будет

+найдено значение $m \geq n$, делающее $m^{2}-n$ квадратом. Процесс не может

+продолжаться бесконечно, потому что в конце концов мы придем к $

+(\frac{n+1}{2})^{2} - n = (\frac{n-1}{2})^{2}$ представлению $n$,

+соответствующее тривиальной факторизации $n=n.1$. Если эта точка достигается без

+обнаружения разности квадратов ранее, то $n$ не имеет других делителей, кроме

+$n$ и $1$, и в этом случае оно является простым числом.

+

+

+\section{Реализация}

+\inputminted{python}{../../lab11/lab11.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test11.png}

+\end{figure}

+

+\end{document}

diff --git a/report/lab11/maker.sh b/report/lab11/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab11/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
diff --git a/report/lab12/images/test12.png b/report/lab12/images/test12.png
new file mode 100644
index 0000000..6004670
--- /dev/null
+++ b/report/lab12/images/test12.png
diff --git a/report/lab12/lab12.pdf b/report/lab12/lab12.pdf
new file mode 100644
index 0000000..baefde4
--- /dev/null
+++ b/report/lab12/lab12.pdf
diff --git a/report/lab12/lab12.tex b/report/lab12/lab12.tex
new file mode 100644
index 0000000..8077040
--- /dev/null
+++ b/report/lab12/lab12.tex
@@ -0,0 +1,89 @@
+\documentclass[a4paper,oneside]{article}

+

+\usepackage[utf8]{inputenc}

+\usepackage[T2A]{fontenc}

+\usepackage[english,russian]{babel}

+

+\usepackage{amsmath}

+\usepackage{mathtools}

+\usepackage{amsfonts}

+\usepackage{enumitem}

+\usepackage{amsthm}

+\usepackage{minted}

+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}

+\usepackage{graphicx}

+\graphicspath{ {./images/} }

+\usepackage{float}

+

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

+\newtheorem*{theorem*}{Теорема}

+

+% --- Определение --- %

+\theoremstyle{definition}

+\newtheorem{definition}{Определение}[subsection]

+\newtheorem*{definition*}{Определение}

+% ------------------- %

+

+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №12}}

+\author{Гущин Андрей, 431 группа, 1 подгруппа}

+\date{\the\year{} г.}

+

+\begin{document}

+

+\maketitle

+

+\section{Задача}

+Осуществить факторизацию с помощью алгоритма Диксона.

+

+

+\section{Алгоритм}

+Алгоритм Диксона — алгоритм факторизации, использующий

+в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел

+$x$ и $y$ таких, что $x^2 \equiv y^2\pmod{n}$ и $x \not\equiv \pm

+y\pmod{n}$. Он является обобщением метода Ферма.

+

+В общем виде алгоритм можно представить следующим образом:

+\begin{enumerate}

+    \item

+        Составить факторную базу ${\displaystyle \mathrm {B}

+        =\left\{{p_{1},p_{2},\dots ,p_{h}}\right\}}$, состоящую из всех

+        простых чисел ${\displaystyle p \leq M = L\left({n}\right)^{\frac

+        {1}{2}}}$, где ${\displaystyle L\left({n}\right)=\exp {\left({\sqrt

+        {\ln {n}\cdot \ln {\ln {n}}}}\right)}}$.

+    \item Выбрать такое случайное $b$, что $\sqrt{n}<b<n$.

+    \item Вычислить $a = b^2\bmod{n}$.

+    \item

+        Проверить число $a$ на гладкость пробными делениями. Если $a$ является

+        $\mathrm{B}$-гладким числом, то есть $a = \prod_{p\in

+        \mathrm{B}}p^{\alpha_{p}\left({b}\right)}$, следует запомнить вектора

+        $\vec{\alpha}(b)$ и $\vec{\varepsilon}(b)$

+    \item

+        Повторять процедуру генерации чисел $b$ до тех пор, пока не

+        будет найдено $h+1$ $\mathrm{B}$-гладких чисел $b_1,...,b_{h+1}$.

+    \item

+        Методом Гаусса найти линейную зависимость среди векторов

+        $\vec{\varepsilon}(b_1), \dots, \vec{\varepsilon}(b_{h+1})$ и положить:

+        \begin{align*}

+        x &= b_{i_1} \dots b_{i_t}\bmod{n} \\

+        y &= \prod_{p \in \mathrm{B}} 

+                p^{\frac{(\alpha_p (b_{i_1}) + \dots + \alpha_p(b_{i_t}))}{2}}\pmod{n}.

+        \end{align*}

+    \item

+        Проверить $x \equiv \pm y \pmod{n}$. Если это так, то повторить

+        процедуру генерации. Если нет, то найдено нетривиальное разложение:

+        \[{\displaystyle n=u\cdot v, u=gcd\left({x+y,n}\right),

+        v=gcd\left({x-y,n}\right).}\]

+\end{enumerate}

+

+

+\section{Реализация}

+\inputminted{python}{../../lab12/lab12.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test12.png}

+\end{figure}

+

+\end{document}

diff --git a/report/lab12/maker.sh b/report/lab12/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab12/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
diff --git a/report/lab13/images/test13.png b/report/lab13/images/test13.png
new file mode 100644
index 0000000..97c5351
--- /dev/null
+++ b/report/lab13/images/test13.png
diff --git a/report/lab13/lab13.pdf b/report/lab13/lab13.pdf
new file mode 100644
index 0000000..db6cbfa
--- /dev/null
+++ b/report/lab13/lab13.pdf
diff --git a/report/lab13/lab13.tex b/report/lab13/lab13.tex
new file mode 100644
index 0000000..61101c7
--- /dev/null
+++ b/report/lab13/lab13.tex
@@ -0,0 +1,75 @@
+\documentclass[a4paper,oneside]{article}

+

+\usepackage[utf8]{inputenc}

+\usepackage[T2A]{fontenc}

+\usepackage[english,russian]{babel}

+

+\usepackage{amsmath}

+\usepackage{mathtools}

+\usepackage{amsfonts}

+\usepackage{enumitem}

+\usepackage{amsthm}

+\usepackage{minted}

+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}

+\usepackage{graphicx}

+\graphicspath{ {./images/} }

+\usepackage{float}

+

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

+\newtheorem*{theorem*}{Теорема}

+

+% --- Определение --- %

+\theoremstyle{definition}

+\newtheorem{definition}{Определение}[subsection]

+\newtheorem*{definition*}{Определение}

+% ------------------- %

+

+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №13}}

+\author{Гущин Андрей, 431 группа, 1 подгруппа}

+\date{\the\year{} г.}

+

+\begin{document}

+

+\maketitle

+

+\section{Задача}

+

+Реализация алгоритма полиномиального деления (PDF).

+

+

+\section{Алгоритм}

+

+На вход алгоритма подаются многочлены $p_1(x) = \sum_0^m c_i x^i$ и $p_2(x) =

+\sum_0^n d_i x^i$ над полем $m \geq n \geq 0$ и $d_n \neq 0$. Этот алгоритм

+будет работать и над областью целостности $J$ при условии, что $d_n$ обратим в

+$J$.

+

+В результате получаем частное $q(x) = \sum_0^{m - n} q_i x^i$ и остаток $r(x) =

+\sum_0^{n - 1} r_i x^i$, обладающие свойством евклидовости.

+

+В общем виде алгоритм можно представить следующим образом:

+\begin{enumerate}

+    \item

+        Основной цикл: для $k$ от $m - n$ до $0$ выполнять $q_k = c_{n + k}

+        \cdot d_n^{-1}$, для $j$ от $n + k - 1$ до $k$ выполнять $c_j = c_j -

+        q_k \cdot d_{j - k}$.

+    \item

+        Выход: вернуть $q_i$, где $i = 0, 1, \dots, m - n$, и коэффициенты

+        полинома $q(x)$, вычисленного на шаге $1$, и $r_j$, где $i = 0, 1,

+        \dots, n - 1$, коэффициенты полинома $r(x)$, где $r_j = c_j$ (где $c_j$

+        также вычислены на шаге $1$).

+\end{enumerate}

+

+

+\section{Реализация}

+\inputminted{python}{../../lab13/lab13.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test13.png}

+\end{figure}

+

+

+\end{document}

diff --git a/report/lab13/maker.sh b/report/lab13/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab13/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
diff --git a/report/lab15/images/test15.png b/report/lab15/images/test15.png
new file mode 100644
index 0000000..a607878
--- /dev/null
+++ b/report/lab15/images/test15.png
diff --git a/report/lab15/lab15.pdf b/report/lab15/lab15.pdf
new file mode 100644
index 0000000..dd9c74e
--- /dev/null
+++ b/report/lab15/lab15.pdf
diff --git a/report/lab15/lab15.tex b/report/lab15/lab15.tex
new file mode 100644
index 0000000..077ba29
--- /dev/null
+++ b/report/lab15/lab15.tex
@@ -0,0 +1,104 @@
+\documentclass[a4paper,oneside]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+
+\usepackage{amsmath}
+\usepackage{mathtools}
+\usepackage{amsfonts}
+\usepackage{enumitem}
+\usepackage{amsthm}
+\usepackage{minted}
+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
+\usepackage{float}
+
+\newtheorem{theorem}{Теорема}[subsection]
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}[subsection]
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №15}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section{Задача}
+
+Вычисление значений и корней полиномов
+
+
+\section{Алгоритм}
+
+
+\subsection{Значение многочлена}
+
+При вычислении значений многочленов очень широкое применение получило правило
+Горнера. Метод назван в честь британского математика Уильяма Джорджа Горнера.
+
+В соответствии с этим правилом многочлен $n$-й степени:
+\begin{equation*}
+    P_n(x)=a_0 x^n + a_1 x^{n-1} + \dots + a_{n-1} x + a_n
+\end{equation*}
+представляется в виде
+\begin{equation*}
+    P_n(x) =(\dots((a_0 x + a_1) x + a_2) x + \dots + a_{n-1}) x + a_n
+\end{equation*}
+
+Вычисление значения многочлена производится в порядке, определяемом скобками.
+
+\subsection{Корни многочлена}
+
+Схема Горнера - способ деления многочлена
+$$P_n(x) = \sum_{i=0}^{n} a_i x^{n - i} = a_0 x^n + a_1 x^{n - 1} + \cdots +
+a_n$$ на бином $x - a$. Работать придётся с таблицей, первая строка которой
+содержит коэффициенты заданного многочлена.  Первым элементом второй строки
+будет число $a$, взятое из бинома $x - a$.
+
+Вторая строка таблицы заполняется постепенно. Второй элемент этой строки
+(обозначим его $b_0$) равен $a_0$, т.е., по сути, мы просто переносим вниз число
+$a_0$.
+
+Следующий элемент второй строки, который мы обозначим как $b_1$, получается по
+такой формуле: $b_1 = a \cdot b_0 + a_1$.  Далее находим элемент $b_2$ по
+формуле $b_2 = a \cdot b_1 + a_2$ и т.д.
+
+В конечном итоге, мы вычислим последний элемент $b_n = a \cdot b_{n - 1} + a_n$.
+
+После деления исходного многочлена $n$-й степени $P_n(x)$ на бином $x - a$,
+получим многочлен, степень которого на единицу меньше исходного, т.е. равна $n -
+1$.
+
+Последнее число второй строки, т.е. $b_n$, есть остаток от деления $P_n ( x )$
+на $x - a$:
+\begin{equation*}
+    \sum_{i=0}^{n} a_i x^{n - i} = a_0 x^n + a_1 x^{n - 1} + \dots + a_n = (x - a) \cdot (b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 1}) + b_n
+\end{equation*}
+
+Таким образом, по теореме Безу это означает, что число $b_n$ равно значению
+многочлена $P_n ( x )$ при $x = a$, т.е. $b_n = P_n ( a )$.
+
+Если $b_n = 0$, то исходный многочлен делится на бином $x - a$ нацело, т.е.
+число $a$ является корнем этого многочлена.
+
+
+\section{Реализация}
+\inputminted{python}{../../lab15/lab15.py}
+
+
+\section{Тестирование}
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=0.8\textwidth]{test15.png}
+\end{figure}
+
+\end{document}
diff --git a/report/lab15/maker.sh b/report/lab15/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab15/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
diff --git a/report/lab7/lab7.tex b/report/lab7/lab7.tex
index b816976..6ce3ee7 100644
--- a/report/lab7/lab7.tex
+++ b/report/lab7/lab7.tex
@@ -36,6 +36,7 @@
 
 Осуществить проверку чисел на простоту с помощью теста Рабина"=Миллера.
 
+
 \section{Алгоритм}
 
 Тест Миллера --- Рабина опирается на проверку ряда равенств, которые выполняются для
@@ -49,12 +50,14 @@
   \item Существует целое число $r < s$ такое что $a^{2^r d} \equiv -1 \pmod{n}$
 \end{enumerate}
 
+
 \section{Реализация}
 
 Для реализации программы использовался язык программирования Rust с системой
 сборки cargo. Для работы с длинной арифметикой использовалась библиотека rug.
 
-\inputminted[fontsize=\small, breaklines=true, style=emacs, linenos]{rust}{../../lab7/src/main.rs}
+\inputminted{rust}{../../lab7/src/main.rs}
+
 
 \section{Тестирование}
 
diff --git a/report/lab8/images/test8.png b/report/lab8/images/test8.png
new file mode 100644
index 0000000..362ab76
--- /dev/null
+++ b/report/lab8/images/test8.png
diff --git a/report/lab8/lab8.pdf b/report/lab8/lab8.pdf
new file mode 100644
index 0000000..0ce50b0
--- /dev/null
+++ b/report/lab8/lab8.pdf
diff --git a/report/lab8/lab8.tex b/report/lab8/lab8.tex
new file mode 100644
index 0000000..8ba3421
--- /dev/null
+++ b/report/lab8/lab8.tex
@@ -0,0 +1,105 @@
+\documentclass[a4paper,oneside]{article}

+

+\usepackage[utf8]{inputenc}

+\usepackage[T2A]{fontenc}

+\usepackage[english,russian]{babel}

+

+\usepackage{amsmath}

+\usepackage{mathtools}

+\usepackage{amsfonts}

+\usepackage{enumitem}

+\usepackage{amsthm}

+\usepackage{minted}

+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}

+\usepackage{graphicx}

+\graphicspath{ {./images/} }

+\usepackage{float}

+

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

+\newtheorem*{theorem*}{Теорема}

+

+% --- Определение --- %

+\theoremstyle{definition}

+\newtheorem{definition}{Определение}[subsection]

+\newtheorem*{definition*}{Определение}

+% ------------------- %

+

+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №8}}

+\author{Гущин Андрей, 431 группа, 1 подгруппа}

+\date{\the\year{} г.}

+

+\begin{document}

+

+

+\maketitle

+

+\section{Задача}

+

+        Осуществить проверку чисел на простоту с помощью

+        полиномиального теста распознавания простоты.

+

+\section{Алгоритм}

+

+        Тест Агравала — Каяла — Саксены (тест AKS) — единственный известный на

+        данный момент универсальный (то есть применимый ко всем числам)

+        полиномиальный, детерминированный и безусловный (то есть не зависящий от

+        недоказанных гипотез) тест простоты чисел, основанный на обобщении малой

+        теоремы Ферма на многочлены.

+

+

+        Если существует ${\displaystyle r\in \mathbb {Z}}$ такое, что

+        ${\displaystyle o_{r}(n)>\log ^{2}n}$ и для любого ${\displaystyle a}$

+        от 1 до ${\displaystyle \left\lfloor {\sqrt {\varphi (r) }} \log(n)

+        \right \rfloor }$ выполняется сравнение ${\displaystyle (x+a)^{n}\equiv

+        (x^{n}+a){\pmod {x^{r}-1,\;n}}}$, то ${\displaystyle n}$ — либо простое

+        число, либо степень простого числа.

+

+        Здесь и далее ${\displaystyle o_{r}(n)}$ обозначает показатель числа

+        ${\displaystyle n}$ по модулю ${\displaystyle r}$, $\log$  — двоичный

+        логарифм и $\varphi (\cdot )$ — функция Эйлера.

+

+        Сравнение по двум модулям вида \[{\displaystyle a(x)\equiv b(x){\pmod

+        {h(x),\;n}}}\] для многочленов ${\displaystyle a(x),\;b(x)\in \mathbb

+        {Z} [x]}$ означает, что существует ${\displaystyle g(x)\in \mathbb {Z}

+        [x]}$ такой, что все коэффициенты многочлена ${\displaystyle a(x) - b(x)

+        - g(x)h(x)}$ кратны $n$, где $\mathbb {Z} [x]$ — кольцо многочленов от

+        $x$ над целыми числами.

+

+        \textbf{Показателем}, или \textbf{мультипликативным порядком}, целого

+        числа $a$ по модулю $m$ называется наименьшее положительное целое число

+        $\ell$, такое, что ${\displaystyle a^{\ell }\equiv 1{\pmod {m}}.}$

+

+

+        В общем виде алгоритм можно представить следующим образом:

+

+        \begin{enumerate}

+            \item Подается на проверку число $n$.

+            \item Проверить, является ли $n$ степенью числа: если $n = a^b$ для

+            целых чисел $a > 1$, $b > 1$. Если да, вернуть ''составное''.

+            \item Найти такое наименьшее $r$ (взаимнопростое с $n$), что

+            $o_{r}(n) > (log_2 \; n)^2$.

+            \item Если $1 < $НОД$(a,\;n) < n$ для некоторого $a \leq r$,

+            вернуть ''составное''.

+            \item Если $n\leq r$, вернуть ''простое''.

+            \item Если для всех $a$ от $1$ до $\left\lfloor {\sqrt {\varphi

+            (r)}}\log(n)\right\rfloor$ верно, что $(x+a)^{n}\equiv x^{n}+a{\pmod

+            {x^{r}-1,\;n}}$, вернуть ''простое''.

+            \item Иначе вернуть ''составное''.

+        \end{enumerate}

+

+        Для вычисления коэффициентов многочлена, полученного из $(x+a)^{n}\equiv

+        x^{n}+a{\pmod {x^{r}-1,\;n}}$, с целью проверки их делимости на

+        исследуемое число $n$ использовался треугольник Паскаля.

+

+

+\section{Реализация}

+\inputminted{python}{../../lab8/lab8.py}

+

+\section{Тестирование}

+

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test8.png}

+\end{figure}

+

+\end{document}

diff --git a/report/lab8/maker.sh b/report/lab8/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab8/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
diff --git a/report/lab9/images/test9.png b/report/lab9/images/test9.png
new file mode 100644
index 0000000..d6bc2e8
--- /dev/null
+++ b/report/lab9/images/test9.png
diff --git a/report/lab9/lab9.pdf b/report/lab9/lab9.pdf
new file mode 100644
index 0000000..ef0efcc
--- /dev/null
+++ b/report/lab9/lab9.pdf
diff --git a/report/lab9/lab9.tex b/report/lab9/lab9.tex
new file mode 100644
index 0000000..b47474a
--- /dev/null
+++ b/report/lab9/lab9.tex
@@ -0,0 +1,80 @@
+\documentclass[a4paper,oneside]{article}

+

+\usepackage[utf8]{inputenc}

+\usepackage[T2A]{fontenc}

+\usepackage[english,russian]{babel}

+

+\usepackage{amsmath}

+\usepackage{mathtools}

+\usepackage{amsfonts}

+\usepackage{enumitem}

+\usepackage{amsthm}

+\usepackage{minted}

+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}

+\usepackage{graphicx}

+\graphicspath{ {./images/} }

+\usepackage{float}

+

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

+\newtheorem*{theorem*}{Теорема}

+

+% --- Определение --- %

+\theoremstyle{definition}

+\newtheorem{definition}{Определение}[subsection]

+\newtheorem*{definition*}{Определение}

+% ------------------- %

+

+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №9}}

+\author{Гущин Андрей, 431 группа, 1 подгруппа}

+\date{\the\year{} г.}

+

+\begin{document}

+

+\maketitle

+

+\section{Задача}

+

+Осуществить построение большого простого числа с

+использованием критерия Люка.

+

+

+\section{Алгоритм}

+

+В теории чисел тест простоты Люка — это тест простоты натурального числа

+n; для его работы необходимо знать разложение $n-1$ на множители. Для

+простого числа n простые множители числа $n-1$ вместе с некоторым

+основанием a составляют сертификат Пратта, который позволяет подтвердить

+за полиномиальное время, что число n является простым.

+

+Пусть n > 1 — натуральное число. Если существует целое $a$ такое, что

+${\displaystyle 1<a<n}$ и

+\[a^{n-1} \equiv 1 \pmod n\] и для любого простого делителя $q$ числа

+$n-1$

+\[{\displaystyle a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}}\] то $n$

+простое.

+

+Если такого числа $a$ не существует, то $n$ — составное число.

+

+Практическая реализация основана на выборе случайного числа в диапазоне значений

+от $2^{b - 1} + 1$ до $2^b - 1$ (где $b$ определяет число бит генерируемого

+простого числа). Далее это число проверяется на наличие небольших простых

+делителей (простые числа меньше 500), и если таких делителей не найдено,

+осуществляется проверка с помощью теста Люка. Если число проходит тест, значит

+оно является сгенерированным простым числом. Если же число не проходит тест или

+у него есть делители среди небольших первых простых чисел, то выбирается другое

+число из этого диапазона, пока выбранное число не будет проходить тест успешно. 

+

+

+\section{Реализация}

+\inputminted{python}{../../lab9/lab9.py}

+

+

+\section{Тестирование}

+\begin{figure}[H]

+    \centering

+    \includegraphics[width=0.8\textwidth]{test9.png}

+\end{figure}

+

+

+

+\end{document}

diff --git a/report/lab9/maker.sh b/report/lab9/maker.sh
new file mode 100755
index 0000000..e847acf
--- /dev/null
+++ b/report/lab9/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