Сравнения по модулю и модулярная арифметика

Осваиваем арифметику остатков — «арифметику часов», на которой держатся хеши, контрольные суммы и криптография.

Числа a и b сравнимы по модулю m (запись a ≡ b (mod m)), если они дают одинаковый остаток при делении на m, то есть m | (a − b).

Зачем нужна модулярная арифметика

Часы показывают время по модулю 12 (или 24): после 23:00 идёт 0:00, а не 24:00. Дни недели циклятся по модулю 7. Эта «циклическая» арифметика — не диковинка, а рабочий инструмент информатики. Хеш-таблицы используют остаток от деления, чтобы распределить ключи по корзинам. Контрольные суммы и коды проверки (включая контрольную цифру в банковских картах) основаны на сравнениях. Криптография RSA — это возведение в степень по модулю. Модулярная арифметика превращает бесконечные числа в конечный, удобный для вычислений мир остатков.

Сравнения: что это значит

Запись 17 ≡ 5 (mod 12) читается «17 сравнимо с 5 по модулю 12» и означает, что 17 и 5 дают одинаковый остаток при делении на 12 (оба дают 5). На циферблате часов 17 часов — это 5 часов пополудни: то же положение стрелки. Сравнение разбивает все целые числа на классы вычетов — мы это уже встречали как отношение эквивалентности! По модулю m таких классов ровно m: {0, 1, ..., m−1}, по остаткам.

Главное свойство: можно считать по остаткам

Модулярная арифметика хороша тем, что сравнения сохраняются при сложении и умножении. Если a ≡ a' (mod m) и b ≡ b' (mod m), то:

• a + b ≡ a' + b' (mod m)
• a · b ≡ a' · b' (mod m)

На практике это золотое правило: можно брать остаток на каждом шаге, а не в самом конце. Это спасает от работы с гигантскими числами — именно так возводят в огромные степени по модулю в криптографии, не вычисляя астрономических промежуточных значений. Проверим это свойство кодом.

# «Часовая» арифметика: 17 часов + 20 часов по модулю 24
print("(17 + 20) mod 24 =", (17 + 20) % 24)

# Свойство: (a * b) mod m == ((a mod m) * (b mod m)) mod m
a, b, m = 123456, 789, 1000
direct = (a * b) % m
stepwise = ((a % m) * (b % m)) % m
print(f"({a} * {b}) mod {m} напрямую   =", direct)
print(f"через остатки на каждом шаге  =", stepwise)
print("Совпадают:", direct == stepwise)

# Можно брать остаток заранее — числа остаются маленькими
print("Последние 3 цифры 7^100:", pow(7, 100, 1000))

Вывод:

(17 + 20) mod 24 = 13
(123456 * 789) mod 1000 напрямую   = 784
через остатки на каждом шаге  = 784
Совпадают: True
Последние 3 цифры 7^100: 1

Считать «в лоб» (123456·789) mod 1000 и «по остаткам» дало одинаковый результат 784 — свойство работает. А последняя строка показывает практическую мощь: pow(7, 100, 1000) мгновенно находит последние три цифры числа 7^100 (у которого 85 знаков!), ни разу не вычисляя его целиком. Встроенная функция pow с третьим аргументом — это и есть быстрое возведение в степень по модулю, сердце криптографии.

Вычитание, деление и обратные элементы

Сложение, вычитание и умножение по модулю работают привычно. А вот деление устроено хитрее: «разделить на a» означает «умножить на обратный элемент a⁻¹», где a · a⁻¹ ≡ 1 (mod m). Обратный по модулю существует не всегда — только когда НОД(a, m) = 1 (число a и модуль взаимно просты). Находят его расширенным алгоритмом Евклида из прошлого урока. Это объясняет, почему в криптографии так важны простые модули: при простом m обратный есть у каждого ненулевого элемента.

# Обратный элемент к 3 по модулю 7: ищем x, где 3*x ≡ 1 (mod 7)
m = 7
for x in range(m):
    if (3 * x) % m == 1:
        print(f"Обратный к 3 по модулю 7: {x}")
        print(f"Проверка: 3 * {x} mod 7 =", (3 * x) % m)
        break

Вывод:

Обратный к 3 по модулю 7: 5
Проверка: 3 * 5 mod 7 = 1

Обратным к 3 по модулю 7 оказалось число 5: 3·5 = 15 ≡ 1 (mod 7). То есть «деление на 3» по модулю 7 — это умножение на 5. Обратные элементы — ключевой механизм расшифровки: в RSA закрытый ключ это, по сути, обратный к открытому по специальному модулю.

Где это работает в реальности

• Хеш-таблицы: индекс корзины = hash(key) % размер_таблицы.
• Контрольные суммы: номер банковской карты проверяется алгоритмом Луна по модулю 10.
• Генераторы псевдослучайных чисел: линейный конгруэнтный метод — это x = (a·x + c) mod m.
• Криптография: RSA шифрует как c = m^e mod n.

RSA: как теория чисел защищает интернет

Всё, что мы изучаем в этом разделе, сходится в одном из главных изобретений XX века — шифровании RSA, на котором держится безопасность интернета (значок замка в браузере — часто это оно). Идея опирается на простую асимметрию: перемножить два больших простых числа легко, а вот разложить их произведение обратно на множители — чудовищно трудно. Если взять два простых по 300 цифр и перемножить, факторизация результата займёт у лучших суперкомпьютеров миллиарды лет.

Из этой асимметрии строится магия: открытый ключ (которым шифруют) можно публиковать всем, а закрытый (которым расшифровывают) знает только владелец, и вычислить его без разложения на множители невозможно. В работе RSA участвует весь наш арсенал: простые числа (их генерируют и проверяют тестами на простоту), НОД и расширенный алгоритм Евклида (для построения ключей), возведение в степень по модулю и малая теорема Ферма (для шифрования и расшифровки). Поэтому теория чисел, веками считавшаяся «самой бесполезной» частью математики, сегодня охраняет каждый ваш платёж и пароль. Об оставшихся кирпичиках RSA — модулярной арифметике и теореме Ферма — следующие два урока.

Типичные ошибки

• Считать, что деление по модулю — это обычное деление. Делить нельзя просто так; нужно умножать на обратный элемент, который существует лишь при взаимной простоте с модулем.
• Забывать про отрицательные остатки. В математике остаток неотрицателен; в некоторых языках (-7) % 3 даёт отрицательное значение. В Python (-7) % 3 == 2 — как в математике, но это не везде так.
• Вычислять огромные степени целиком. Нужно брать остаток на каждом шаге (или использовать pow(a, b, m)), иначе числа станут неподъёмными.

Итог

• a ≡ b (mod m) означает одинаковый остаток при делении на m; это отношение эквивалентности с m классами.
• Сравнения сохраняются при сложении и умножении — можно брать остаток на каждом шаге.
• Деление по модулю — это умножение на обратный элемент, существующий при НОД(a, m) = 1.
• Модулярная арифметика лежит в основе хешей, контрольных сумм и криптографии.