forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
euclidean_algorithm.tex
100 lines (84 loc) · 5.57 KB
/
euclidean_algorithm.tex
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
\subsection{Алгоритм Евклида}\index{алгоритм!Евклида}
\selectlanguage{russian}
Рекурсивная форма алгоритма Евклида вычисления $\gcd(a,b)$ имеет следующий вид:
\[\set(a,b): a>b; \gcd(a,b) = \gcd(b, a \mod b). \]
Редуцирование чисел продолжается, пока не получим
\[ a \mod b = 0, \]
тогда $b$ и будет искомым НОД.
\example
Вычислим $\gcd(56, 35)$:
\[ \begin{array}{ll}
\gcd(56, 35) & =~ \gcd(35, ~ 56 \mod 35 = 21) ~= \\
& =~ \gcd(21, ~ 35 \mod 21 = 14) ~= \\
& =~ \gcd(14, ~ 21 \mod 14 = 7) ~= \\
& =~ \gcd(7, ~ 14 \mod 7 = 0) ~= \\
& =~ 7. \\
\end{array} \]
\exampleend
\subsection{Расширенный алгоритм Евклида}\index{алгоритм!Евклида!расширенный}
\emph{Расширенный алгоритм Евклида} (см., например,~\cite[8.8 Наибольшие общие делители и алгоритм Евклида]{Aho:1979}) для целых $a, b, a > b$ находит
\[ x, y, d = \gcd(a,b): ax + by = d. \]
Введём обозначения: $g_i$ -- частное от деления, $r_i$ -- остаток от деления на $i$-ом шаге. Алгоритм:
\[\begin{array}{ll}
r_{-1} & := a, \\
r_0 & := b, \\
y_0 & := x_{-1} := 1, \\
y_{-1} & := x_0 := 0. \\
\end{array}\]
\[\begin{array}{ll}
g_i & := \left\lfloor r_{i-2} / r_{i-1} \right\rfloor, \\
r_i & := r_{i-2} - g_i \cdot r_{i-1}, \\
y_i & := y_{i-2} - g_i \cdot y_{i-1} , \\
x_i & := x_{i-2} - g_i \cdot x_{i-1} . \\
\end{array}\]
Алгоритм останавливается, когда $r_i = 0$.
%Вычисление осуществляется точно так же, как и в обычном алгоритме Евклида, только на каждой итерации дополнительно находится частное и остаток от деления.
\example
В таблице~\ref{tab:extended-euclid} приведён числовой пример алгоритма для $a=136, b=36$.
\begin{table}[!ht]
\centering
\caption{Пример расширенного алгоритма Евклида для \\ $a=136, b=36$\label{tab:extended-euclid}}
\begin{tabular}{|r|r|r|r|r|rrr|}
\hline
$i$ & $g_i$ & $r_i$ & $x_i$ & $y_i$ & & & \\
\hline
$-1$ & --- & $136$ & $1$ & $0$ & $136 =$ & $ 1 \cdot 136$ & $ + 0 \cdot 36$ \\
$0$ & --- & $36$ & $0$ & $1$ & $36 =$ & $ 0 \cdot 136$ & $ + 1 \cdot 36$ \\
$1$ & $3$ & $28$ & $+1$ & $-3$ & $28 =$ & $+1 \cdot 136$ & $ - 3 \cdot 36$ \\
$2$ & $1$ & $8$ & $-1$ & $+4$ & $8 =$ & $-1 \cdot 136$ & $ + 4 \cdot 36$ \\
$3$ & $3$ & $4$ & $+5$ & $-19$ & $-4 =$ & $+5 \cdot 136$ & $- 19 \cdot 36$ \\
$4$ & $2$ & $0$ & --- & --- & & & --- \\
\hline
\end{tabular}
\end{table}
Найдено $x = 5, ~ y = -19, ~ d = 4$.
\exampleend
\subsection[Нахождение мультипликативного обратного]{Нахождение мультипликативного \protect\\ обратного по модулю}
Расширенный алгоритм Евклида можно использовать для вычисления обратного элемента\index{обратный элемент}: для заданных $a, n$ найти $x, y, d = \gcd(a,n): ax + ny = d$. Пусть $a,n$ -- взаимно простые, тогда
\[\begin{array}{l}
ax + ny = 1, \\
ax \equiv 1 \mod n, \\
x \equiv a^{-1} \mod n. \\
\end{array}\]
\example
В таблице~\ref{tab:extended-euclid-inverse} приведён числовой пример вычисления расширенным алгоритмом Евклида для $a=142, b=33$ обратных элементов $33^{-1} \equiv -43 \mod 142$ и $142^{-1} \equiv 10 \mod 33$.
\begin{table}[!ht]
\centering
\caption{Пример вычисления обратных элементов $33^{-1} \equiv -43 \mod 142$ и $142^{-1} \equiv 10 \mod 33$ из уравнения $142 x + 33 y = 1$ расширенным алгоритмом Евклида\label{tab:extended-euclid-inverse}}
\begin{tabular}{|r|r|r|r|r|rrr|}
\hline
$i$ & $g_i$ & $r_i$ & $x_i$ & $y_i$ & & & \\
\hline
$-1$ & --- & $142$ & $1$ & $0$ & $142 =$ & $ 1 \cdot 142$ & $ + 0 \cdot 33$ \\
$0$ & --- & $33$ & $0$ & $1$ & $33 =$ & $ 0 \cdot 142$ & $ + 1 \cdot 33$ \\
$1$ & $4$ & $10$ & $+1$ & $-4$ & $10 =$ & $ +1 \cdot 142$ & $ - 4 \cdot 33$ \\
$2$ & $3$ & $3$ & $-3$ & $+13$ & $3 =$ & $ -3 \cdot 142$ & $+ 13 \cdot 33$ \\
$3$ & $3$ & $1$ & $+10$ & $-43$ & $1 =$ & $+10 \cdot 142$ & $- 43 \cdot 33$ \\
$4$ & $3$ & $0$ & --- & --- & & & --- \\
\hline
\end{tabular}
\end{table}
\exampleend
Для $k$-битового числа $n$ битовая сложность вычисления обратного элемента имеет порядок $O(k^2)$. Если известно разложение числа $n$ на множители, то по теореме Эйлера
\[ a^{-1} = a^{\varphi(n) - 1} \mod n, \]
и вычисление обратного элемента реализуется с битовой сложностью $O(k^3),~ k = \lceil \log_2 n \rceil$. Сложность вычислений по этому алгоритму можно уменьшить, если известно разложение на сомножители числа $\varphi(n) - 1$.