\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}