Калькулятор китайской теоремы об остатках
Посчитайте груду предметов тройками — останется 2, пятёрками — останется 3, семёрками — останется 2: их 23, или 128, или 233, по одному ответу на каждые 105. Это задача из «Сунь-цзы суань цзин», давшая имя китайской теореме об остатках. Введите любую систему сравнений x ≡ a (mod n), со сколькими угодно сравнениями и сколь угодно большими числами, и посмотрите ответ, решение на ваших числах и рисунок, объясняющий, почему всё работает. Если сравнения не могут выполняться все вместе, калькулятор называет два противоречащих и показывает почему. Введите сравнения x ≡ a (mod n), по одному в строке: a — остаток, n — модуль. Добавьте строку кнопкой «Добавить сравнение» или клавишей Enter в последнем модуле, удалите кнопкой ×. Подходят целые числа до 200 цифр, a может быть отрицательным. Или выберите разобранный пример. Плитки показывают наименьшее решение и через сколько оно повторяется; под ними — первые положительные решения и проверка каждого сравнения. Рисунок отмечает числа, удовлетворяющие каждому сравнению, и столбец, где отметка есть в каждой строке, — это решение; таблица остатков показывает сразу два сравнения. Решение расписано на ваших числах, учебной конструкцией или подстановкой.
Как это работает
- Введите сравнения x ≡ a (mod n), по одному в строке, или выберите разобранный пример: задачу Сунь-цзы, корзину с яйцами или юлианский период.
- Прочитайте наименьшее решение, модуль, с которым оно повторяется, и первые положительные решения, каждое проверенное во всех сравнениях.
- Следите за решением шаг за шагом, конструкцией или подстановкой, и переключайте рисунок между числовой прямой и таблицей остатков.
Как работает конструкция
Когда никакие два модуля не имеют общего делителя, решение можно построить напрямую. Перемножьте модули: в задаче Сунь-цзы N = 3 × 5 × 7 = 105. Для каждого сравнения возьмите Nᵢ = N / nᵢ, кратное всем остальным модулям: 35, 21 и 15. Затем найдите обратный yᵢ к Nᵢ по модулю nᵢ расширенным алгоритмом Евклида: 35 при делении на 3 даёт остаток 2, а 2 × 2 = 4 ≡ 1 (mod 3), поэтому y₁ = 2; 21 и 15 дают остаток 1, поэтому их обратные равны 1. Тогда x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, а 233 mod 105 = 23. Каждое слагаемое подходит к своему сравнению и кратно остальным модулям, поэтому сумма подходит ко всем.
Когда у модулей есть общий делитель
Система, у модулей которой есть общие делители, тоже может иметь решение. Два сравнения x ≡ a (mod m) и x ≡ b (mod n) выполняются одновременно ровно тогда, когда a − b кратно gcd(m, n), и тогда решение повторяется через каждые lcm(m, n), а не через m × n. Два автобуса, которые отправляются на 5-й и 11-й минутах, каждые 12 и каждые 18 минут, встречаются на 29-й минуте и затем каждые 36 минут, потому что 11 − 5 = 6 кратно gcd(12, 18) = 6. Но x ≡ 1 (mod 4) и x ≡ 4 (mod 6) никогда не выполняются вместе: первое делает x нечётным, второе — чётным. Вся система имеет решение ровно тогда, когда его имеет каждая пара её сравнений, и именно так калькулятор находит два противоречащих.
Часто задаваемые вопросы
Что утверждает китайская теорема об остатках?
Если никакие два из модулей n₁, n₂, … не имеют общего делителя, то для любых остатков a₁, a₂, … существует ровно одно x от 0 до N − 1, для которого x ≡ aᵢ (mod nᵢ) при каждом i, где N — произведение модулей. Любое другое решение отличается от него на кратное N: в задаче Сунь-цзы решения — 23, 128, 233 и так далее, по одному на каждые 105.
Почему она называется китайской?
Самая древняя известная задача такого рода есть в «Сунь-цзы суань цзин», китайской книге по арифметике, написанной между III и V веками: при счёте тройками, пятёрками и семёрками некие предметы дают остатки 2, 3 и 2. Цинь Цзюшао дал общий метод для таких задач в 1247 году, а Карл Фридрих Гаусс сформулировал теорему в современном виде в 1801 году.
А если модули не взаимно просты?
Тогда решения может не быть, а если оно есть, то повторяется через наименьшее общее кратное модулей, а не через их произведение. Два сравнения согласованы, когда их остатки совпадают по модулю gcd их модулей. В задаче про яйца используются 2, 3, 4, 5, 6 и 7, у которых есть общие делители, и всё же решение есть: 301, повторяющееся через каждые 420.
Как RSA использует китайскую теорему об остатках?
Расшифровать сообщение RSA — значит вычислить c^d mod n, где n = p × q. Быстрее вычислить отдельно c^d mod p и c^d mod q, с показателем, приведённым по модулю p − 1 и q − 1, и соединить два результата теоремой. С числами вдвое короче каждое из двух возведений в степень требует около одной восьмой работы, поэтому расшифровка примерно в четыре раза быстрее, и большинство программ RSA делает именно так.
Насколько большими могут быть числа?
До 20 сравнений, числа — до 200 цифр каждое. Калькулятор считает точными целыми числами в вашем браузере, поэтому ответ точен при любой длине, и ничего никуда не отправляется.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор