1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
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}
|
