From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 29 Dec 2022 15:20:32 +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=BB=D0=B0=D0=B1=D1=8B=208-15?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 report/lab1/images/test.png | Bin 0 -> 424255 bytes
 report/lab1/lab1.pdf        | Bin 0 -> 450567 bytes
 report/lab1/lab1.tex        |  90 ++++++++++++++++++++++++++++++++++++++++++++
 report/lab1/lab1.xdv        | Bin 0 -> 18696 bytes
 report/lab1/maker.sh        |  35 +++++++++++++++++
 5 files changed, 125 insertions(+)
 create mode 100644 report/lab1/images/test.png
 create mode 100644 report/lab1/lab1.pdf
 create mode 100644 report/lab1/lab1.tex
 create mode 100644 report/lab1/lab1.xdv
 create mode 100755 report/lab1/maker.sh

(limited to 'report/lab1')

diff --git a/report/lab1/images/test.png b/report/lab1/images/test.png
new file mode 100644
index 0000000..3425735
Binary files /dev/null and b/report/lab1/images/test.png differ
diff --git a/report/lab1/lab1.pdf b/report/lab1/lab1.pdf
new file mode 100644
index 0000000..ce1df61
Binary files /dev/null and b/report/lab1/lab1.pdf differ
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
Binary files /dev/null and b/report/lab1/lab1.xdv differ
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
-- 
cgit v1.2.3