Арифметика
Модулярная арифметика
Часы показывают 10, через 5 часов будет 3, а не 15 - это модулярная арифметика в действии. Та же математика защищает интернет-пароли, банковские переводы и государственные секреты. Арифметика остатков - одна из самых практичных ветвей теории чисел.
- **Криптография:** RSA, цифровые подписи
- **Хеширование:** распределение данных, контрольные суммы
- **Повседневность:** часы, дни недели, расписания
Операция mod
Операция «по модулю» лежит в основе почти любой безопасной транзакции в интернете: RSA-шифрование (Rivest-Shamir-Adleman, 1977) работает по модулю 2048-битных чисел, а криптография на эллиптической кривой secp256k1 (используется в Bitcoin с 2009 года) - по модулю 256-битного простого числа. К 2024 году около 95 процентов интернет-трафика защищено модулярной арифметикой такого рода.
Операция **mod** (модуль) возвращает остаток от деления. Это «циклическая» арифметика: после определённого значения числа начинаются заново.
**Операция mod:** a mod n = остаток от деления a на n 17 mod 5 = 2 (потому что 17 = 3×5 + 2) 23 mod 7 = 2 (потому что 23 = 3×7 + 2)
Модулярная арифметика - это арифметика «по кругу». После n-1 снова идёт 0, как на циферблате часов.
Чему равно 47 mod 7?
Сравнения по модулю
Два числа **сравнимы по модулю n**, если у них одинаковые остатки от деления на n. Записывается: a ≡ b (mod n).
**Символ ≡ (конгруэнтность):** Не путать с равенством (=)! 17 ≠ 2, но 17 ≡ 2 (mod 5) Это разные числа, но «одинаковые по модулю 5».
Сравнения по модулю - язык теории чисел. Они позволяют работать с бесконечными множествами, рассматривая только остатки.
Какое утверждение верно?
Операции по модулю
Сложение, вычитание и умножение работают с модулями естественным образом. Можно вычислять mod на каждом шаге - результат не изменится.
**Практическое применение:** Криптография RSA использует операции: m^e mod n (шифрование) c^d mod n (расшифровка) Где n - произведение двух больших простых чисел.
Модулярное возведение в степень - основа современной криптографии. Легко вычислить, но обратить (найти показатель) - практически невозможно.
Чему равно (7 × 8) mod 10?
Применения
Модулярная арифметика окружает нас: часы, дни недели, хеш-функции, контрольные суммы, криптография.
**Китайская теорема об остатках:** Если n₁, n₂, ..., nₖ попарно взаимно просты, то система сравнений: x ≡ a₁ (mod n₁) x ≡ a₂ (mod n₂) ... имеет единственное решение по модулю n₁×n₂×...×nₖ.
Модулярная арифметика - мост между школьной математикой и современной криптографией. Банковские переводы и HTTPS-рукопожатия защищены именно этими идеями (RSA, ECDSA).
Остаток от деления на n всегда меньше n
Остаток от деления на n принадлежит множеству {0, 1, ..., n-1}
Это верное утверждение, но его часто забывают! Остаток всегда неотрицателен и строго меньше делителя. 17 mod 5 = 2 (не -3, хотя 17 = 4×5 + (-3) тоже верно арифметически). По соглашению, остаток - всегда от 0 до n-1.
Сегодня понедельник. Какой день недели будет через 1000 дней?
Ключевые идеи
- a mod n - остаток от деления a на n
- a ≡ b (mod n) - одинаковые остатки
- +, -, × работают естественно по модулю
- Основа современной криптографии
Связанные темы
Модулярная арифметика связана с теорией чисел:
- Делимость — Остатки и деление
- НОК — Китайская теорема об остатках
- Простые числа — RSA криптография
Вопросы для размышления
- Почему модулярное возведение в степень - основа криптографии?
- Как модуль 7 связан с днями недели?
- Почему деление по модулю сложнее других операций?