| определение | a mod n = r, где a = q·n + r, 0 ≤ r < n |
| примеры | 17 mod 5 = 2 · 100 mod 7 = 2 · 2256 mod p |
| применение | RSA · хэш-функции · музыкальные гаммы · цикличность |
| в Sonic Pi | (ring 0,1,2,3,4).tick — это mod под капотом |
| парадокс | −1 mod 5 = 4 в математике, но −1 в C/Java |
| связано | простые числа · XOR · факториал |
Оператор, который делает числа круглыми.
mod — это не просто остаток. это способ превратить бесконечную числовую прямую в окружность.
17 mod 12 = 5. Именно так работают часы — 17:00 это 5 часов вечера. Mod превращает линейное время в циклическое: после 12 счёт начинается сначала. Та же операция превращает числовую прямую в окружность из n точек.
Эта простая идея лежит в основе криптографии RSA. Шифрование — это возведение в степень по модулю произведения двух больших простых: c = me mod n. Расшифровка — m = cd mod n. Надёжность RSA опирается на то, что по c, e, n восстановить m вычислительно сложно — нужно факторизовать n, а это в общем случае никто не умеет делать быстро1.
Mod — это не остаток. Это координата на окружности.
Mod появляется везде, где есть цикличность: дни недели (mod 7), байты (mod 256), музыкальные гаммы (mod 12). В Sonic Pi каждый ring — это структура с mod под капотом: `(ring 60, 62, 64, 65).tick` возвращает элементы по кругу именно через mod от счётчика тиков.
Есть тонкость, на которой ломаются программисты: как трактовать отрицательные числа. В математике −1 mod 5 = 4 (остаток всегда неотрицателен, в диапазоне [0, n)). В C, Java, Python 2 знак остатка следует знаку делимого: −1 mod 5 = −1. В Python 3 — снова 4, по математическому соглашению. Один и тот же оператор, разные языки, разные ответы — источник тонких багов в сетевом коде2.
Малая теорема Ферма: для простого p и a, не кратного p, ap−1 mod p = 1. Из этого вырастает вся модулярная арифметика — и RSA в том числе3. Один маленький оператор — и треть современной криптографии.