\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{setspace,amsmath}
\usepackage{amssymb}
\begin{document}
\textbf{Теорема 2.4} \;\; \large Обобщённый алгоритм Евклида
\\\\
\normalsize ВХОД: \;\;\; Положительные целые числа $a,b, a \geq b$.
\\
ВЫХОД: \;\; $gcd(a, b), x, y$ Удовлетворяющие условию теоремы 2.9).
\begin{enumerate}
\item $U \leftarrow (a,1,0), V \leftarrow (b,0,1)$.
\item WHILE $\; v_1\ne0\; DO$
\item $\;\;\;\;\;\;\; q\; \leftarrow u_1\,div\,v_1\,$;
\item $\;\;\;\;\;\;\; T \leftarrow (u_1 mod v_1 , v_2 - qv_2, u_3 - qv_3)$;
\item $\;\;\;\;\;\;\; U \leftarrow V, V \leftarrow T $
\item RETURN $U = (gcd(a, b), x, y)$.
\end{enumerate}
Результат содержится в строке $U$.
\\
Операция div в алгоритме - это целочисленное деление ($a div b = [a/b]$). Доказательство корректности этого алгоритма может быть найдено в [1, 9].
\\
П\,р\,и\,м\,е\,р 2.12. \;\; Пусть $a = 28, b =19$. Найдём числа $x$ и $y$, удовлетаворяющие условию теоремы 2.9.
\begin{center}
\begin{tabular}{c c c c c c c c}
U & & & & 28 & 1 & 0 &
\\
V & U & & & 19 & 0 & 1 &
\\
T & V & U & & 9 & 1 & -1& q = 1
\\
& T & V & U & 1 & -2 & 3 & q = 2
\\
& & T & V & 0 & -17&-28& q = 9
\\
\end{tabular}
\end{center}
Поясним представленную схему. Вначале в строку $U$ записываются числа $(28, 1, 0)$, а в строку $V$ - числа $(19, 0, 1)$ (это первые две строки на схеме). Вычисляется строка $T$ (третья строка в схеме). После этого в качестве строки $U$ берётся вторая строка в схеме, а в качестве $V$ - третья, и опять вычисляется $T$ (четвёртая строка в схеме). Этот процесс продолжается до тех пор, пока первый элемент строки $V$ не станет равным нулю. Тогда предпоследняя строка в схеме содержит ответ. В нашем слуаче $gcd(28, 19) = 1, x = -2, y = 3$. Выполним проверку: $28\cdot(-2) + 19\cdot3 = 1$.
\\\\
Рассмотрим одно важное применение обобщённого алгоритма Евклида. Во многих задачах криптографии для заданных чисел c, m требуется находить такое число $d < m$, что
\begin{equation}
cd\, mod\, m = 1.
\end{equation}
\\
Отметим, что такое $d$ существует тогда и только тогда, когда $c$ и $m$ - взаимно простые числа.
\\\\
\textbf{Определение 2.6} Число $d$, удовлетворяющее условию $cd\, mod\, m = 1$, называется \emph{инверсией c по модулю m} и часто обозначается $c^{-1}\,mod\,m$.
\\\\
Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать $cd\, mod\, m = 1$ в виде
\begin{gather*}
\bar cc^{-1}\,mod m\, = 1.
\end{gather*}
\\
Умножение на $c^{-1}$ соответсвует делению на $c$ при вычислениях по модулю $m$. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю $m$:
\begin{gather*}
\bar c^{-e} = {(c^{e})}^{-1} = {(c^{-1})}^e \,mod\, m.
\end{gather*}
\\
П\,р\,и\,м\,е\,р 2.13. \;\; $3\cdot4 mod 11 = 1$, поэтому число 4 - это инверсия числа 3 по модулю 11. Можно записать $3^{-1}\,mod\,11 = 4 $. Число $5^{-2}\,mod\,11$ может быть найдено двумя способами:
\begin{gather*}
\bar 5^{-2}\,mod\,11 = (5^{-2}\,mod\,11)^{-1}\,mod\,11 = 3^{-1}\,mod\,11 = 4,
\\\\
\bar 5^{-2}\,mod\,11 = (5^{-1}\,mod\,11)^{2}\,mod\,11 = 9^{2}\,mod\,11 = 4.
\end{gather*}
При вычислениях по второму способу мы использовали равенство $5^{-1}\,mod\,11 = 9$. Действительно, $5\cdot9\,mod\,11 = 45\,mod\,11 = 1$.
\\
Покажем, как можно вычислить инверсию с помощью обобщённого алгоритма Евклида. Равенство (2.12) означает, что для некоторого целого $k$
\begin{equation}
cd - km = 1.
\end{equation}
\\
Учитывая, что $c$ и $m$ взаимно просты, перепишем последнее равенство в виде
\begin{equation}
m(-k) + cd = gcd(m, c).
\end{equation}
\\
что полностью соответствует условию теоремы 2.9, здесь только по-другому обозначены переменные. Поэтому чтобы вычислить $c^{-1}\,mod\,m$, то есть найти число $d$, нужно просто использовать обобщённый алгоритм Евклида для решения уравнения $m(-k) + cd = gcd(m, c)$. Заметим, что значение переменной $k$ нас не интересует, поэтому можно не вычислять вторые элементы строк $U, V, T$. Кроме того, если число $d$ получается отрицательным, то нужно прибавить к нему $m$, так как по определению число $a\,mod\,m$ берётся из множества $\{0,1,.....,m -1\}$.
\end{document}
