2 files changed, 139 insertions, 0 deletions
diff --git a/reports/lab3/lab3.pdf b/reports/lab3/lab3.pdf
new file mode 100644
index 0000000..f37bbc1
--- /dev/null
+++ b/reports/lab3/lab3.pdf
diff --git a/reports/lab3/lab3.tex b/reports/lab3/lab3.tex
new file mode 100644
index 0000000..46063aa
--- /dev/null
+++ b/reports/lab3/lab3.tex
@@ -0,0 +1,139 @@
+\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}