\documentclass[a4paper,oneside]{article}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}

\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{amsthm}

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

% --- Определение --- %
\theoremstyle{definition}
\newtheorem{definition}{Определение}[subsection]
\newtheorem*{definition*}{Определение}
% ------------------- %

\date{}


\title{Криптографические методы защиты информации, Лабораторная работа №3}
\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}

\begin{document}

\maketitle

Факторизацией натурального числа называется его разложение в произведение
простых множителей. Существование и единственность (с точностью до порядка
следования множителей) такого разложения следует из \textbf{основной теоремы
арифметики}.

Простой перебор множителей является довольно неэффективным алгоритмом,
особенно для достаточно больших чисел. В таком случае необходимо выбрать другой
алгоритм разложения на множители.

Например, таким является алгоритм Шермана Лемана.

Пусть $n$ нечётно и $n > 8$.
\begin{enumerate}
    \item
        Для $a = 2, 3, \dots, \lfloor n^{1/3} \rfloor$ проверить условие
        $a | n$. Если на этом шаге не удалось разложить $n$ на множители,
        то переходим к следующему шагу.

    \item
        Если на предыдущем шаге делитель не найден и $n$ --- составное, то $n =
        pq$, где $p, q$ --- простые числа, и $n^{1/3} < p \leq q < n^{2/3}$.
        Тогда для всех $k = 1, 2, \dots, \lfloor n^{1/3} \rfloor$ и для всех
        $d = 0, \dots, \left\lfloor \frac{n^{1/6}}{4 \sqrt{k}} \right\rfloor + 1$
        проверить, является ли число $(\lfloor \sqrt{4kn} \rfloor + d)^2 - 4kn$
        квадратом натурального числа. Если является, то для $A = \lfloor \sqrt{4kn} \rfloor + d$ и
        $B = \sqrt{A^2 - 4kn}$ выполнено сравнение:
        \[ A^2 \equiv B^2 \pmod n \text{ или } (A - B)(A + B) \equiv 0 \pmod n \]

        В этом случае для $d^* = \gcd(A - B, n)$ проверяется неравенство
        $1 < d^* < n$. Если оно выполнено, то $n = d^* \cdot (n / d^*)$ --- разложение $n$ на два множителя.

        Если алгоритм не нашёл разложение $n$ на два множителя, то $n$ --- простое число.
\end{enumerate}

Можно заметить, что данный алгоритм имеет временную сложность $O(n^{1/3})$,
что является более эффективным результатом по сравнению с простым перебором
множителей, который имеет временную сложность $O(n^{1/2})$.

Рассмотрим алгоритм для $n_1 = 21894583143407671$. $\lfloor n_1^{1/3} \rfloor
= \lfloor 21894583143407671^{1/3} \rfloor = \lfloor 279755.66757 \rfloor =
279755$. Перебрав все простые числа $a = 2, 3, \dots, 279755$ и проверив
для каждого $(n_1 | a)$, я заметил, что ни одно из них не является простым
множителем числа 21894583143407671. Таким образом, переходим ко второму шагу
алгоритма.

Снова будем перебирать все числа $k = 1, 2, 3, \dots, 279755$ и для каждого $k$
вычислим значение $\left\lfloor \frac{n_1^{1/6}}{4 \sqrt{k}} \right\rfloor +
1 = \left\lfloor \frac{21894583143407671^{1/6}}{4 \cdot \sqrt{k}} \right\rfloor
+ 1 = \left\lfloor \frac{528.91934}{4 \cdot \sqrt{k}} \right\rfloor + 1$.

Далее необходимо перебрать все $d = 0, \dots, \left\lfloor \frac{n_1^{1/6}}{4
\sqrt{k}} \right\rfloor + 1$.

Пусть $k = 1$, $d_{max} = \left\lfloor \frac{528.91934}{4 \cdot \sqrt{1}}
\right\rfloor = \left\lfloor \frac{528.91934}{4} \right\rfloor =
\left\lfloor 132.22983 \right\rfloor = 132$

Для каждого $d = 0, \dots, 132$ необходимо проверить является ли число
$(\lfloor \sqrt{4kn} \rfloor + d)^2 - 4kn$ полным квадратом натурального числа.

Для $k = 1, d = 0$ это число равно $(\lfloor \sqrt{4 \cdot 1 \cdot
21894583143407671} \rfloor + 0)^2 - 4 \cdot 1 \cdot 21894583143407671 =
(\lfloor \sqrt{4 \cdot 1 \cdot 21894583143407671} \rfloor + 0)^2 - 4 \cdot 1
\cdot 21894583143407671 = (\lfloor 295936365.75053 \rfloor)^2 -
87578332573630688 = 295936365^2 - 87578332573630688 = -444217463$.

Отрицательное число не может быть квадратом натурального числа, поэтому
продолжаем перебор.

$\dots$

Пусть $k = 26304$, $d_{max} = \left\lfloor \frac{528.91934}{4 \cdot \sqrt{26304}}
\right\rfloor = \left\lfloor \frac{528.91934}{162.18508} \right\rfloor =
\left\lfloor 3.26121 \right\rfloor = 3$

$\dots$

Для $k = 26304, d = 1$ это число равно $(\lfloor \sqrt{4 \cdot 26304 \cdot
21894583143407671} \rfloor + 1)^2 - 4 \cdot 26304 \cdot 21894583143407671 =
(\lfloor \sqrt{2303660460016781511936} \rfloor + 1)^2 - 2303660460016781511936
= (\lfloor 47996462994.858086 \rfloor + 1)^2 - 2303660460016781511936 =
47996462995^2 - 2303660460016781511936 =
2303660460030404370025 - 2303660460016781511936 = 13622858089$.

Число 13622858089 является полным квадратом числа 116717.

Вычислим $A = \lfloor \sqrt{4 * k * n} \rfloor + d$ и $B = \sqrt{A^2 - 4kn}$:

$A = \lfloor \sqrt{4 \cdot 26304 \cdot 21894583143407671} \rfloor + 1 = 
47996462995$.

$B = \sqrt{47996462995^2 - 4 \cdot 26304 \cdot 21894583143407671} = 116717$.

Выполним сравнение $A^2 \equiv B^2 \pmod n$.

$47996462995^2 \equiv 116717^2 \pmod {21894583143407671} =
2303660460030404370025 \equiv 13622858089 \pmod {21894583143407671} =
13622858089 \equiv 13622858089 \pmod {21894583143407671}$.

Так как это выражение верно, вычислим $d^* = \gcd(A - B, n) =
\gcd(47996462995 - 116717, 21894583143407671) =
\gcd(47996346278, 21894583143407671) = 175169147$

Для данного $d^*$ выполняется равенство $1 < d^* < n$, значит это число является
множителем числа $n$, а вторым множителем является число $n / d^* = 124991093$.


\end{document}