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/lab1.tex | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)
 create mode 100644 report/lab1/lab1.tex

(limited to 'report/lab1/lab1.tex')

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}
-- 
cgit v1.2.3

