modular_ariphmetics.tex

\section{Модульная арифметика}
\selectlanguage{russian}

\subsection{Сложность модульных операций}

Криптосистемы с открытым ключом, как правило, построены в модульной арифметике с  длиной модуля от сотни до нескольких тысяч разрядов. Сложность алгоритмов оценивают как количество битовых операций в зависимости от длины. В табл. \ref{tab:mod-binary-complexity} приведены оценки (с точностью до порядка) сложности модульных операций\index{битовая сложность} для простых (или "школьных") алгоритмов вычислений. На самом деле, для реализации арифметики длинных чисел (сотни или тысячи двоичных разрядов) следует применять существенно более эффективные (более "хитрые") алгоритмы вычислений, использующие, например, специальный вид быстрого преобразования Фурье и другие приемы.

\begin{table}[h!]
    \centering
    \caption{Битовая сложность операций по модулю $n$ длиной $k= \log n$ бит\label{tab:mod-binary-complexity}}
    \begin{tabular}{| p{0.7\textwidth} | c |}
        \hline
        Операция, алгоритм & Сложность \\
        \hline
        1. $a \pm b \mod n$ & $O(k)$ \\
        2. $a \cdot b \mod n$ & $O(k^2)$ \\
        3. $\gcd(a, b)$, алгоритм Евклида & $O(k^2)$ \\
        4. $(a,b) \rightarrow (x,y,d) : ax + by = d = \gcd(a,b)$, расширенный алгоритм Евклида & $O(k^2)$ \\
        5. $a^{-1} \mod n$, расширенный алгоритм Евклида & $O(k^2)$ \\
        6. Китайская теорема об остатках & $O(k^2)$ \\
        7. $a^b \mod n$ & $O(k^3)$ \\
        \hline
    \end{tabular}

\end{table}


\subsection{Возведение в степень по модулю}

Метод называется <<возводи в квадрат и перемножай>>. Найдем $a^b \mod n$.
    \[ b = \sum_{i=0}^{k-1} b_i 2^i, \]
    \[ a^b = a^{\sum\limits_{i=0}^{k-1} b_i 2^i} = \prod_{i=0}^{k-1} (a^{{2^i} b_i} \mod n) \mod n. \]
Последовательно вычисляем квадраты
    \[ a_0 = a, ~ a_1 = a_0^2 \mod n, ~ a_2 = a_1^2 \mod n,  \ldots  \]
по модулю $n$ и перемножаем $a_i$, которым соответствует $b_i = 1$.  Число возведений в квадрат равно $k-1$ (если $b_{k-1} =1$), а число умножений меньше или равно $k-1$. Возведение в квадрат и умножение можно считать операцией с квадратичной битовой сложностью $O(k^2)$. Поэтому общая битовая сложность возведения в степень -- кубическая
    \[ O(2(k-1)k^2) = O(k^3). \]

\example
\[ \begin{array}{l}
    8^{24} \mod 25 = 8^8 \cdot 8^{16} \mod 25, \\
    8^2 = 14, \\
    8^4 = -4, \\
    8^8 = 16, \\
    8^{16} = 6, \\
    8^{24} = 16 \cdot 6 = -4 \mod 25.
\end{array} \]
\exampleend