Калькулятор модульной арифметики

Арифметика остатков

Число a mod m — это остаток от деления a на m, всегда от 0 до m − 1 (для отрицательных a тоже: −7 mod 5 = 3). Числа, дающие одинаковые остатки, называют сравнимыми по модулю: 17 ≡ 2 (mod 5). Сложение, вычитание и умножение можно выполнять прямо с остатками — результат по модулю не изменится. На этом построены часы, контрольные цифры номеров, хеш-таблицы и почти вся криптография с открытым ключом.

Возведение в степень по модулю

Число 7¹²⁸ содержит 109 цифр, но остаток 7¹²⁸ mod 13 находится за несколько шагов. Показатель записывают в двоичном виде, основание последовательно возводят в квадрат (a, a², a⁴, a⁸…), беря остаток на каждом шаге, и перемножают те степени, которым соответствует единица в двоичной записи. Для показателя из k бит нужно не больше 2k умножений — так RSA и Диффи — Хеллман работают с числами в тысячи бит.

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

Обратный к a по модулю m — такое число x, что a · x ≡ 1 (mod m). Он существует, только если НОД(a, m) = 1. Расширенный алгоритм Евклида находит коэффициенты Безу — целые x и y, для которых a · x + m · y = НОД(a, m). Если НОД равен 1, то x и есть обратный элемент. Например, 3⁻¹ mod 7 = 5, потому что 3 · 5 = 15 = 2 · 7 + 1.

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

Если модули попарно взаимно просты, система сравнений x ≡ r₁ (mod m₁), …, x ≡ r_k (mod m_k) имеет единственное решение по модулю M = m₁ · … · m_k. Классическая задача Сунь-цзы: число при делении на 3 даёт остаток 2, на 5 — 3, на 7 — 2. Ответ: 23 (и все числа 23 + 105k). Калькулятор решает и системы с не взаимно простыми модулями, если они совместны.

Малая теорема Ферма

Если p — простое и a не делится на p, то a^p−1 ≡ 1 (mod p). Отсюда обратный элемент по простому модулю: a⁻¹ ≡ a^p−2 (mod p). На этой теореме основаны тесты простоты, которые используются при генерации ключей RSA.