euclidean_algorithm.tex

\subsection{Алгоритм Евклида}
\selectlanguage{russian}

Рекурсивная форма Алгоритма Евклида\index{алгоритм!Евклида} вычисления $\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{алгоритм!расширенный Евклида} для целых $a,b$ находит
    \[ Q, P, d = \gcd(a,b): aQ + Pb = d. \]
Введем обозначения: $r_i$ -- остаток от деления, $g_i$ -- частное от деления на $i$-ом шаге.

Алгоритм:
\[r_{i-2} = g_i r_{i-1}+r_i , r_{-1} = a, r_0 = b\]
\[P_i = -P_{i-1} g_i + P_{i-2}, Q_i = -Q_{i-1} g_i + Q_{i-2}, P_0 = Q_{-1} = 1, P_1 = Q_0 = 0.\]
Алгоритм останавливается, когда $r_i = 0$.

%Вычисление осуществляется точно так же, как и в обычном алгоритме Евклида, только на каждой итерации дополнительно находится частное и остаток от деления.

\example
В табл. \ref{tab:extended-euclid} приведен числовой пример алгоритма для $a=136, b=36$.
\begin{table}[h!]
    \centering
    \caption{Пример расширенного алгоритма Евклида для \\ $a=136, b=36$\label{tab:extended-euclid}}
    \resizebox{\textwidth}{!}{ \begin{tabular}{|c|c|c|p{0.55\textwidth}|}
        \hline
        Шаг & Частное & Остаток & Подстановка \\
        \hline
        1 & 3 & 28 & $28 = 136 - 3 \cdot 36$ \\
        2 & 1 & 8  & $8 = 36 - 1 \cdot 28 = 36 - 1 \cdot (136 - 3 \cdot 36) = -1 \cdot 136 + 4 \cdot 36$ \\
        3 & 3 & 4  & $4 = 28 - 3 \cdot 8  = 28 - 3 \cdot (-1 \cdot 136 + 4 \cdot 36) = 4 \cdot 136 - 15 \cdot 36$ \\
        4 & 2 & 0  & $4 \cdot 136 - 15 \cdot 36 = 4 = \gcd(136,36)$ \\
        \hline
    \end{tabular} }
\end{table}
Найдено $x = 4, ~ y = -15, ~ d = 4$.
\exampleend

\subsection[Нахождение мультипликативного обратного]{Нахождение мультипликативного \protect\\ обратного по модулю}

Для вычисления обратного элемента\index{обратный элемент} можно использовать расширенный алгоритм Евклида -- для заданных $a, n$ найти $x, y, d = \gcd(a,n): ax + ny = d$. Пусть $a,n$ -- взаимно простые, тогда
    \[ ax + ny = 1, ~~ ax = 1 \mod n, ~ \Rightarrow ~ x = a^{-1} \mod n. \]
Для $k$-битового $n$ битовая сложность вычисления обратного элемента имеет порядок $O(k^2)$.

\example
В табл. \ref{tab:extended-euclid-inverse} приведен числовой пример вычисления расширенным алгоритмом Евклида для $a=142, b=33$ обратных $33^{-1} = -43 \mod 142$, или же $142^{-1} = 10 \mod 33$.

\begin{table}[h!]
    \centering
    \caption{Пример вычисления обратного элемента \\ $33^{-1}  = -43 \mod 142$\label{tab:extended-euclid-inverse}}
    \begin{tabular}{|c|c|c|l|}
        \hline
        Шаг & Частное & Остаток & Подстановка \\
        \hline
        1 & 4 & 10 & $10 = 142 - 4 \cdot 33$ \\
        2 & 3 & 3  & $3 = 33 - 3 \cdot 10 = -3 \cdot 142 + 13 \cdot 33$ \\
        3 & 3 & 1  & $1 = 10 - 3 \cdot 3 = 10 \cdot 142 - 43 \cdot 33$ \\
        4 & 3 & 0  & $10 \cdot 142 - 43 \cdot 33 = 1 = \gcd(142,33)$ \\
        \hline
    \end{tabular}
\end{table}
\exampleend

Если известно разложение числа $n$ на множители, то по теореме Эйлера
    \[ a^{-1} = a^{\varphi(n) - 1} \mod n \]
и вычисление обратного элемента реализуется с битовой сложностью $O(k^3),~ k = \lceil \log_2 n \rceil$. Сложность вычислений по этому алгоритму можно уменьшить, если известно разложение на сомножители числа $\varphi(n) - 1$.