Модулярная арифметика

При использовании HTTPS браузер и сервер за доли секунды согласуют ключ шифрования через RSA или ECDH. В основе - модулярная арифметика: операции над числами размером 2048 бит, которые математически «оборачиваются» по кольцу ℤₙ. Без теоремы Ферма и быстрого возведения в степень RSA работал бы часами.

• **RSA шифрование:** шифрование c = mᵉ mod n и дешифровка m = cᵈ mod n - применение теоремы Эйлера
• **Хеш-таблицы:** функция index(key) = hash(key) % table_size - сюръекция через модуль
• **Конкурентное программирование:** ответы задач часто по модулю 10⁹+7 (простое), что позволяет использовать теорему Ферма для деления
• **Протокол Диффи-Хеллмана:** обмен ключами через дискретное логарифмирование в ℤₚ

Предварительные знания

• Functions: Injections, Surjections, Bijections

Сравнения и кольцо ℤₙ

Говорят, что a ≡ b (mod n), если n делит (a - b), то есть a и b дают одинаковый остаток при делении на n. Множество остатков {0, 1, 2, ..., n-1} с операциями сложения и умножения по модулю n образует кольцо ℤₙ.

**Свойства сравнений:** если a ≡ b (mod n) и c ≡ d (mod n), то: - a + c ≡ b + d (mod n) - a · c ≡ b · d (mod n) - aᵏ ≡ bᵏ (mod n) Это значит, что арифметические операции можно «делать по ходу» - не накапливать большие числа.

В программировании операция % - это остаток от деления, но в Python он всегда неотрицательный (совпадает с математическим mod). В C/Java (-7) % 3 = -1 (знак совпадает с делимым), а не 2. При работе с криптографией всегда используйте Python или явно нормализуйте: ((a % n) + n) % n.

В C, C++, Java операция % для отрицательных чисел возвращает отрицательный результат: -7 % 3 == -1, а не 2. В Python: -7 % 3 == 2 (математически корректно). В криптографических реализациях на C всегда добавляйте нормализацию: (a % n + n) % n.

Теоремы Ферма и Эйлера

Малая теорема Ферма: если p - простое число и gcd(a, p) = 1, то aᵖ⁻¹ ≡ 1 (mod p). Теорема Эйлера обобщает это: если gcd(a, n) = 1, то aᵠ⁽ⁿ⁾ ≡ 1 (mod n), где φ(n) - функция Эйлера (число целых от 1 до n, взаимно простых с n).

**Функция Эйлера φ(n):** - φ(p) = p - 1 для простого p - φ(p·q) = (p-1)(q-1) для различных простых p, q - φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ⁻¹(p-1) - Мультипликативность: если gcd(m,n)=1, то φ(mn) = φ(m)·φ(n)

В RSA используется теорема Эйлера: если n = p·q (p, q - различные простые), то φ(n) = (p-1)(q-1). Выбирается открытая экспонента e с gcd(e, φ(n)) = 1, и закрытая d такая, что e·d ≡ 1 (mod φ(n)). Шифрование: c = mᵉ mod n, дешифровка: m = cᵈ mod n.

Тест Ферма на простоту: если aⁿ⁻¹ ≢ 1 (mod n) для некоторого a, то n - не простое. Но числа Кармайкла проходят тест Ферма для всех a! Для надёжного теста нужен Миллер-Рабин.

Быстрое возведение в степень

Задача: вычислить a^n mod m, где n может быть огромным (например, 10¹⁸). Наивный алгоритм - n умножений - непригоден. Метод «возведения в квадрат» (square-and-multiply) работает за O(log n) умножений.

**Ключевая идея (бинарная экспонентация):** - a^0 = 1 - a^(2k) = (a^k)² - если степень чётная, делим надвое - a^(2k+1) = a · (a^k)² - если нечётная, отдельный множитель На каждом шаге берём mod m, чтобы числа не росли.

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

Китайская теорема об остатках (CRT)

Китайская теорема об остатках (CRT): если n₁, n₂, ..., nₖ попарно взаимно просты (gcd(nᵢ, nⱼ) = 1 при i ≠ j), то система сравнений x ≡ aᵢ (mod nᵢ) имеет единственное решение по модулю N = n₁·n₂·...·nₖ.

**Конструктивное решение CRT:** N = n₁·n₂·...·nₖ Nᵢ = N / nᵢ yᵢ = Nᵢ⁻¹ mod nᵢ (обратный элемент) x = (Σ aᵢ · Nᵢ · yᵢ) mod N Каждое слагаемое aᵢ·Nᵢ·yᵢ ≡ aᵢ (mod nᵢ) и ≡ 0 (mod nⱼ) при j ≠ i.

CRT используется в: RSA-CRT оптимизации (в 4 раза быстрее стандартного RSA), параллельных вычислениях (независимые вычисления по разным модулям объединяются), теории кодирования, и в системах контроля версий Git (объединение конфликтующих изменений аналогично восстановлению числа по остаткам).

CRT - это изоморфизм колец: ℤₙ ≅ ℤₙ₁ × ℤₙ₂ × ... × ℤₙₖ при попарно взаимно простых nᵢ. Это значит, операции можно делать покомпонентно - отсюда и ускорение RSA: работаем с числами размером p и q отдельно, вместо n = p·q.

Ключевые идеи

• **Сравнения a ≡ b (mod n):** арифметические операции совместимы с mod; позволяют не накапливать большие числа
• **Теорема Ферма:** aᵖ⁻¹ ≡ 1 (mod p) - основа нахождения обратных элементов и теста простоты
• **Функция Эйлера φ(n):** φ(p·q) = (p-1)(q-1) - сердце RSA
• **Быстрое возведение в степень:** O(log n) вместо O(n) - обязательно для любой криптографии
• **Китайская теорема об остатках:** единственное решение системы сравнений; ускоряет RSA в 4×

Связанные темы

Модулярная арифметика - мост между чистой математикой и прикладной криптографией:

• Функции и биекции — RSA шифрование - биекция в кольце ℤₙ; обратимость гарантируется теоремой Эйлера
• Рекуррентные соотношения — Последовательности Фибоначчи по модулю p имеют период (период Пизано); используется в хешировании
• Теория графов — Алгоритм Диффи-Хеллмана строит граф дискретного логарифма; атаки через детектирование циклов

Вопросы для размышления

• В конкурентном программировании ответы часто берут по модулю 10⁹+7. Почему выбрано именно это простое число? Как теорема Ферма помогает делить числа по этому модулю?
• RSA с маленькими ключами (p = 61, q = 53) легко взламывается перебором. Почему при p, q порядка 2^1024 задача становится вычислительно неразрешимой? Какая математическая задача лежит в основе стойкости RSA?
• Хеш-функция key % table_size работает плохо, если table_size - степень двойки и ключи выровнены. Почему? Как выбор простого числа в качестве table_size улучшает распределение?

Связанные уроки

• alg-25-rabin-karp
• alg-33-randomized
• crypto-03-number-theory
• crypto-24-rsa-math
• crypto-26-ecc-math