Модульное возведение в степень

Модульное возведение в степень — это операция возведения целого числа в целую неотрицательную степень по модулю, то есть вычисление значения \(a^b \pmod{n}\), где \(a\) — основание, \(b\) — показатель степени, \(n\) — модуль. Результатом является остаток от деления \(a^b\) на \(n\). Данная операция широко используется в криптографии, теории чисел и алгоритмах, где требуется эффективное вычисление больших степеней без непосредственного возведения в степень, которое может привести к числам огромного размера.

Определение и основные свойства

Формально, модульное возведение в степень определяется как: \[ a^b \bmod n = r, \quad 0 \le r < n, \] где \(r\) — остаток от деления \(a^b\) на \(n\). Операция обладает свойствами, вытекающими из свойств модульной арифметики:

• Коммутативность не выполняется: \(a^b \bmod n \neq b^a \bmod n\) в общем случае.
• Ассоциативность не применима напрямую, но для произведения степеней справедливо: \(a^{b+c} \bmod n = (a^b \bmod n) \cdot (a^c \bmod n) \bmod n\).
• Дистрибутивность относительно умножения: \((a \cdot b)^c \bmod n = (a^c \bmod n) \cdot (b^c \bmod n) \bmod n\).
• При \(n = 1\) результат всегда равен 0, так как любое число делится на 1 без остатка.

Алгоритмы вычисления

Наивное возведение

Наивный способ — вычислить \(a^b\) как обычное целое число, затем взять остаток от деления на \(n\). Однако при больших \(b\) (например, \(b \approx 10^{100}\)) это невозможно из-за экспоненциального роста размера числа. Поэтому применяются более эффективные методы.

Алгоритм быстрого возведения в степень (бинарный метод)

Самый распространённый алгоритм — бинарное возведение в степень (также известное как возведение в степень по квадрату). Он основан на представлении показателя \(b\) в двоичной системе счисления: \[ b = \sum_{i=0}^{k-1} b_i \cdot 2^i, \quad b_i \in \{0, 1\}. \] Тогда \(a^b = a^{\sum b_i 2^i} = \prod_{i=0}^{k-1} a^{b_i \cdot 2^i}\). Алгоритм последовательно возводит основание в квадрат на каждом шаге и умножает результат на текущее значение, если соответствующий бит показателя равен 1. Псевдокод: `` function modpow(a, b, n): result = 1 a = a mod n while b > 0: if b % 2 == 1: result = (result a) mod n a = (a a) mod n b = b // 2 return result `` Время работы — \(O(\log b)\) операций умножения по модулю, что делает его эффективным даже для показателей порядка \(10^{300}\).

Алгоритм Монтгомери

Для ускорения операций умножения по модулю в криптографических системах (например, RSA) используется алгоритм Монтгомери. Он заменяет деление на модуль на более быстрые операции сдвига и сложения, работая в системе счисления по основанию \(R\), где \(R\) — степень двойки, большая модуля. Алгоритм требует предварительного преобразования чисел в форму Монтгомери, но при многократных операциях (например, в цепочке возведений) даёт существенный выигрыш в скорости.

Метод «слепого» возведения

В некоторых приложениях, например, в криптографии с открытым ключом, используется слепое возведение (blinding), когда основание умножается на случайное число, чтобы скрыть его от атак по времени или по энергопотреблению. После вычисления результат корректируется обратным преобразованием.

Применение

Криптография

Модульное возведение в степень является основой многих криптографических систем:

• RSA: шифрование и цифровая подпись основаны на вычислении \(c = m^e \bmod n\) (шифрование) и \(m = c^d \bmod n\) (дешифрование), где \(e\) и \(d\) — открытая и закрытая экспоненты, \(n\) — произведение двух больших простых чисел.
• Диффи-Хеллман: протокол обмена ключами использует \(g^a \bmod p\) и \(g^b \bmod p\) для генерации общего секрета.
• Эль-Гамаль: шифрование на основе дискретного логарифма, где требуется возведение в степень по модулю простого числа.
• DSA (Digital Signature Algorithm): подпись сообщений с использованием модульного возведения.

Теория чисел

В теории чисел модульное возведение применяется для:

• Проверки простоты чисел (тест Ферма, тест Миллера — Рабина).
• Вычисления обратных элементов по модулю через малую теорему Ферма: \(a^{-1} \bmod p = a^{p-2} \bmod p\) для простого \(p\).
• Решения сравнений и дискретных логарифмов.

Вычислительная математика

В алгоритмах, требующих работы с большими числами (например, в символьных вычислениях или в задачах комбинаторики), модульное возведение позволяет избежать переполнения памяти.

Примеры

Пример 1: вычисление \(3^{13} \bmod 7\)

Бинарный метод: \(13_{10} = 1101_2\).

• Шаг 1: \(a = 3\), result = 1, b = 13.
• b нечётное: result = 1 * 3 mod 7 = 3, a = 3^2 mod 7 = 9 mod 7 = 2, b = 6.
• b чётное: a = 2^2 mod 7 = 4, b = 3.
• b нечётное: result = 3 * 4 mod 7 = 12 mod 7 = 5, a = 4^2 mod 7 = 16 mod 7 = 2, b = 1.
• b нечётное: result = 5 * 2 mod 7 = 10 mod 7 = 3, a = 2^2 mod 7 = 4, b = 0.

Результат: \(3^{13} \bmod 7 = 3\).

Пример 2: проверка простоты числа 341

Тест Ферма: \(2^{340} \bmod 341\). Вычисление: \(2^{340} \bmod 341 = 1\). Однако 341 = 11 * 31 — составное число, поэтому тест даёт ложноположительный результат (число Кармайкла).

Сложность и оптимизации

Вычислительная сложность

Бинарный алгоритм выполняет \(O(\log b)\) умножений, каждое из которых требует \(O(\log^2 n)\) битовых операций при наивном умножении. С использованием алгоритмов быстрого умножения (например, Карацубы или Шёнхаге — Штрассена) сложность может быть снижена до \(O(\log b \cdot \log n \cdot \log \log n)\).

Параллельные вычисления

В современных криптографических системах (например, в аппаратных ускорителях) модульное возведение может быть распараллелено с помощью алгоритмов, таких как «Montgomery ladder», который устойчив к атакам по времени.

Интересные факты

• Малая теорема Ферма утверждает, что для простого \(p\) и целого \(a\), не кратного \(p\), выполняется \(a^{p-1} \equiv 1 \pmod{p}\). Это свойство лежит в основе многих криптографических протоколов.
• В алгоритме RSA показатель степени \(e\) часто выбирают равным 65537, так как это простое число Ферма, что ускоряет возведение за счёт малого числа единичных битов в двоичном представлении.
• Модульное возведение в степень может быть выполнено с помощью рекурсивного алгоритма «разделяй и властвуй», но бинарный метод обычно предпочтительнее из-за меньшего числа операций.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007.
• Менезес А., ван Орсхот П., Ванстон С. Прикладная криптография. — М.: Триумф, 2002.
• Стинсон Д. Криптография. Теория и практика. — М.: ДМК Пресс, 2015.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. — 3-е изд. — М.: Вильямс, 2013.