\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{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №7}}
\author{Гущин Андрей, 431 группа, 1 подгруппа}
\date{\the\year{} г.}

\begin{document}

\maketitle

\section{Задача}

Осуществить проверку чисел на простоту с помощью теста Рабина"=Миллера.


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

Тест Миллера --- Рабина опирается на проверку ряда равенств, которые выполняются для
простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает
что число составное.

Пусть $n$ --- простое число и $n - 1 = 2^{s} d$, где $d$ --- нечётно. Тогда для
любого $a$ из $\mathbb{Z}_n$ выполняется хотя бы одно из условий:
\begin{enumerate}
  \item $a^d \equiv 1 \pmod{n}$
  \item Существует целое число $r < s$ такое что $a^{2^r d} \equiv -1 \pmod{n}$
\end{enumerate}


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

Для реализации программы использовался язык программирования Rust с системой
сборки cargo. Для работы с длинной арифметикой использовалась библиотека rug.

\inputminted{rust}{../../lab7/src/main.rs}


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

\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{test.png}
\end{figure}

\end{document}