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

RSA шифрует каждое сообщение в интернете. Приватный ключ - это d такое, что ed ≡ 1 (mod phi(n)). Вычислить d - значит найти обратный элемент в Z/phi(n)Z через расширенный алгоритм Евклида. Весь HTTPS, каждая кредитная карта, каждый пароль - держатся на операции a^{-1} mod n. Алгоритм Евклида (около 300 лет до н.э.) работает в каждом браузере планеты.

• **RSA / ECDSA:** приватный ключ d вычисляется через обратный элемент mod phi(n); Bitcoin-транзакции подписываются в Z/pZ над 256-битным простым
• **SHA-256, MurmurHash:** цепочки операций mod 2^32 и mod 2^64 как лавинообразный эффект внутри хеш-функций; consistent hashing в distributed systems - кольцо Z/n
• **RSA-CRT оптимизация:** ускорение дешифрования в четыре раза через раздельное вычисление mod p и mod q с восстановлением по КТО
• **Secret sharing Шамира:** федеративное обучение без центра - секрет распределяется между участниками через интерполяцию в Z/pZ

Сунь-Цзы и подсчёт армии

Первое упоминание Китайской теоремы об остатках - в книге Сунь-Цзы (III-V вв. н.э.): «Неизвестное число. При делении на три - остаток два, на пять - остаток три, на семь - остаток два. Каково число?» Ответ: двадцать три. Легенда говорит, что полководцы строили солдат по три, по пять, по семь - и по остаткам восстанавливали численность без прямого подсчёта. Эйлер и Гаусс формализовали метод в XVIII-XIX веках.

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

• Алгоритм Евклида и НОД

Сравнения и кольцо Z/nZ

RSA шифрует каждое сообщение в интернете. Приватный ключ - это d такое, что ed ≡ 1 (mod phi(n)). Весь HTTPS, каждая кредитная карта, каждый пароль - держатся на операции a^{-1} mod n. И операция эта строится из одной идеи: два числа, отличающиеся на кратное n, - одно и то же.

**Сравнение:** a ≡ b (mod n) тогда и только тогда, когда n делит (a - b), то есть a и b дают одинаковый остаток при делении на n. Примеры: 17 ≡ 2 (mod 5), -3 ≡ 4 (mod 7), 100 ≡ 0 (mod 10) **Свойства** - если a ≡ b и c ≡ d (mod n), то: - a + c ≡ b + d (mod n) - a * c ≡ b * d (mod n) - a^k ≡ b^k (mod n)

Хеш-функции внутри делают то же самое. SHA-256 - это цепочка операций mod 2^32 и mod 2^64: сложение, битовые сдвиги, таблицы констант. MurmurHash3 использует умножения mod 2^32 как лавинообразный эффект. Consistent hashing в distributed systems работает в кольце Z/n, где n - размер виртуального пространства.

Сравнения сохраняют сложение и умножение - но не деление. 6 ≡ 0 (mod 6), 3 ≡ 3 (mod 6), однако делить обе части на 3 нельзя в лоб: 2 ≢ 0 (mod 6). Деление по модулю - это умножение на обратный элемент, и оно существует не всегда.

Классы вычетов и структура Z/nZ

Класс вычетов - не «остаток». Это целый пучок чисел: ..., -10, -3, 4, 11, 18, ... - все дают остаток 4 при делении на 7. Их бесконечно много, но модульная арифметика видит их как одно число. Это не метафора - это структура: конечное множество {0, 1, ..., n-1} с операциями + и * по модулю.

**Кольцо вычетов Z/nZ:** - Элементы: {0, 1, 2, ..., n-1} - Сложение: (a + b) mod n - Умножение: (a * b) mod n - Нейтральный по +: 0 - Нейтральный по *: 1 **Z/nZ - поле тогда и только тогда, когда n простое** (каждый ненулевой элемент обратим)

Когда n - простое, Z/pZ - это конечное поле GF(p). AES-256 работает в GF(2^8): каждый байт - элемент поля, ShiftRows и MixColumns - линейные операции над ним. Reed-Solomon коды (QR-коды, CD, RAID-6) тоже опираются на GF(2^8). Конечные поля - это не экзотика теормата, а рабочая математика каждого хранилища данных.

Группа обратимых элементов Z/nZ* = {a : gcd(a, n) = 1}. Её порядок - функция Эйлера phi(n). Для простого p: phi(p) = p - 1 (все ненулевые обратимы). Для n = p*q: phi(n) = (p-1)(q-1). Именно эта формула - сердце RSA.

Обратный элемент и расширенный Евклид

Число a^{-1} mod n - это x такое, что a*x ≡ 1 (mod n). Оно существует тогда и только тогда, когда gcd(a, n) = 1 (тождество Безу). Расширенный алгоритм Евклида находит его за O(log n) шагов - и именно он запускается каждый раз при установлении TLS-соединения: сервер вычисляет d = e^{-1} mod phi(n).

**Модулярный обратный:** a^{-1} mod n - число x из {1, ..., n-1} такое, что a*x ≡ 1 (mod n). **Существует тогда и только тогда, когда gcd(a, n) = 1.** **Три способа найти:** 1. Расширенный Евклид: ax + ny = 1 - тогда x = a^{-1} mod n 2. Формула Эйлера: a^{-1} ≡ a^{phi(n)-1} (mod n) 3. Для простого p: a^{-1} ≡ a^{p-2} (mod p) (малая теорема Ферма)

Bitcoin-транзакции подписываются через ECDSA над Z/pZ, где p - 256-битное простое. Подпись включает вычисление k^{-1} mod p - обратного к случайному nonce. Если использовать один и тот же nonce дважды, приватный ключ восстанавливается просто. Именно так взломали Sony PlayStation 3 в 2010 году: фиксированный nonce в ECDSA - и все приватные ключи устройств оказались скомпрометированы.

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

III-V век н.э. Китайский математик Сунь-Цзы пишет задачу: «Неизвестное число. При делении на три - остаток два. На пять - остаток три. На семь - остаток два. Каково число?» Ответ: двадцать три. Но настоящий ответ - не число, а метод: зная остатки по нескольким попарно взаимно простым модулям, можно восстановить число целиком.

**Китайская теорема об остатках (КТО):** Если n1, n2, ..., nk попарно взаимно просты, то система: x ≡ a1 (mod n1) x ≡ a2 (mod n2) ... x ≡ ak (mod nk) имеет **единственное** решение по модулю N = n1 * n2 * ... * nk. **Конструкция:** N_i = N / n_i, тогда x = sum(a_i * N_i * N_i^{-1} mod n_i) mod N

RSA использует КТО для ускорения дешифрования в четыре раза. Вместо c^d mod n (n - 2048-битное число), вычисляют c^d mod p и c^d mod q по отдельности - числа вдвое короче, возведение в степень в четыре раза быстрее. Затем КТО восстанавливает результат mod n. Это RSA-CRT оптимизация, встроенная в OpenSSL.

Схема secret sharing Шамира - распределение секрета без центрального хранителя - тоже использует КТО. Секрет разбивается на k частей так, что любые t из них восстанавливают его через интерполяцию в Z/pZ, а t-1 частей не дают никакой информации. Federated learning применяет аналогичную идею для агрегации градиентов без раскрытия локальных данных.

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

• **Сравнения:** a ≡ b (mod n) - одинаковые остатки; сохраняют +, *, но не деление без оговорок
• **Z/nZ:** кольцо вычетов; Z/pZ - поле (GF(p)), если p простое - основа AES и Reed-Solomon
• **Обратный элемент:** a^{-1} mod n существует тогда и только тогда, когда gcd(a,n) = 1; расширенный Евклид за O(log n)
• **КТО:** система с попарно взаимно простыми модулями имеет единственное решение mod N = произведение модулей

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

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

• Алгоритм Евклида и НОД — Расширенный Евклид - основной инструмент нахождения обратного элемента
• Делимость и простые числа — Простые модули дают поля GF(p); структура Z/nZ определяется факторизацией n
• Малая теорема Ферма — Альтернативный способ вычислить a^{-1} mod p через возведение в степень

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

• Почему RSA использует модуль n = p*q (произведение двух простых), а не просто большое простое? Что теряется с phi(p) и что приобретается с phi(p*q)?
• Алгоритм Евклида (около 300 лет до н.э.) запускается в OpenSSL при каждом TLS-рукопожатии. Сколько раз в секунду он выполняется во всём интернете прямо сейчас?
• Как схема secret sharing Шамира использует интерполяцию в Z/pZ для того, чтобы t-1 участников не могли восстановить секрет, а t - могли?

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

• nt-02 — Расширенный Евклид - единственный инструмент для нахождения a^{-1} mod n
• nt-04 — Малая теорема Ферма задаёт альтернативный путь к обратному элементу
• nt-01 — Простые модули дают поля; составные - кольца с делителями нуля
• alg-01-big-o — O(log n) расширенного Евклида - тот же класс, что двоичный поиск
• prob-04-bayes — КТО и теорема Байеса - оба восстанавливают целое из частичной информации
• crypto-02-modular-arithmetic