Китайская теорема об остатках: большое число как несколько маленьких

Если ты соберёшь число по остаткам через обратные элементы, объяснишь, почему модули обязаны быть взаимно простыми, и знаешь, что соберётся, если результат больше произведения модулей, - листай до «Теперь сам».

Как думаешь, одно ли такое число

Задаче около полутора тысяч лет. Есть число. При делении на 3 оно даёт остаток 2, при делении на 5 - остаток 3, при делении на 7 - остаток 2. Что это за число?

Перебором находится 23. Прежде чем читать дальше, ответь себе на два вопроса. Единственное ли это число? И как найти его без перебора, если модули - не 3, 5 и 7, а числа по сто цифр?

На что это похоже

Представь три лампы, которые мигают с разным периодом: первая загорается каждые 3 секунды, вторая каждые 5, третья каждые 7. В момент ноль горят все три. Посмотрев на каждую лампу, можно сказать, сколько секунд прошло с её последней вспышки, - это остаток времени по её периоду.

Одна лампа говорит о времени мало: первая не отличает секунду 2 от секунды 5. Но три лампы вместе повторяют одну и ту же картину только через 3 · 5 · 7 = 105 секунд. Внутри этих 105 секунд каждая картина встречается ровно один раз, и по трём остаткам время восстанавливается точно.

Если бы периоды были 4 и 6, картина повторялась бы уже через 12 секунд, а не через 24: у периодов есть общий делитель, и часть сведений лампы дублируют.

Механизм: единственность и сборка

Почему число одно. Пусть у x и y одинаковые остатки по всем модулям. Тогда разность x − y делится на каждый модуль. Модули попарно взаимно просты - общих простых множителей у них нет, поэтому в разложении разности на простые множители каждый модуль присутствует своими, отдельными множителями, и разность делится на их произведение M. Два разных числа от 0 до M − 1 различаются меньше чем на M, поэтому одинаковых наборов остатков у них быть не может. Чисел M, наборов остатков тоже M - каждому набору достаётся ровно одно число.

Как собрать. Для каждого модуля нужен «выключатель» - число, которое по своему модулю даёт 1, а по всем остальным 0. Тогда ответ - сумма «остаток на выключатель».

модули 3, 5, 7        M = 105

модуль mᵢ    Mᵢ = M / mᵢ    Mᵢ mod mᵢ    обратный    выключатель eᵢ = Mᵢ · обратный
   3            35             2            2              70       (70 ≡ 1 по модулю 3; делится на 5 и 7)
   5            21             1            1              21       (21 ≡ 1 по модулю 5; делится на 3 и 7)
   7            15             1            1              15       (15 ≡ 1 по модулю 7; делится на 3 и 5)

x = 2 · 70 + 3 · 21 + 2 · 15 = 233          233 mod 105 = 23

Mᵢ - произведение всех модулей, кроме своего: оно уже делится на остальные, то есть даёт по ним 0. Остаётся сделать из него единицу по своему модулю - умножить на обратный к нему по mᵢ. Обратный существует как раз потому, что Mᵢ и mᵢ взаимно просты. Здесь и видно, зачем условие: без него не построить выключатель.

Правило

Китайская теорема об остатках. Пусть модули m₁, …, m_k попарно взаимно просты и M - их произведение. Тогда для любых остатков r₁, …, r_k существует ровно одно число x от 0 до M − 1 с x ≡ rᵢ (mod mᵢ) для всех i, и оно равно Σ rᵢ · Mᵢ · (Mᵢ⁻¹ mod mᵢ) по модулю M, где Mᵢ = M / mᵢ. Сложение, вычитание и умножение чисел по модулю M можно выполнять отдельно над каждым остатком.

Знак Σ - сумма по всем i.

Разбор: программа сборки

def kto(ostatki, moduli):
    M = 1
    for m in moduli:
        M = M * m
    x = 0
    i = 0
    while i < len(moduli):
        m = moduli[i]
        Mi = M // m
        k = ostatki[i] * obratnyj(Mi % m, m) % m
        x = (x + k * Mi) % M
        i = i + 1
    return [x, M]

Функция obratnyj - из урока про расширенный алгоритм Евклида, она возвращает одно число. Множитель k приведён по модулю m до умножения на Mi: так произведение k * Mi всегда меньше M и не выходит за точность.

kto([2, 3, 2], [3, 5, 7]) возвращает [23, 105]. Ответ на первый вопрос из начала: до 105 такое число одно, а дальше подходят 128, 233 и все числа через 105. Ответ на второй: сборка - это по одному вызову алгоритма Евклида на модуль, длина модулей ей не страшна.

Ещё пример с двумя модулями: kto([1, 2], [4, 9]) возвращает [29, 36]. Число 29 даёт остаток 1 при делении на 4 и остаток 2 при делении на 9.

Разбор: умножение по частям и где оно ломается

Перемножим a = 123 456 и b = 654 321 так, чтобы сами эти числа встречались только по частям - четырёхзначное на четырёхзначное. Модули - три простых числа: 9973, 9967 и 9949.

модуль      a mod m     b mod m     (a mod m) · (b mod m) mod m
9 973        3 780       6 076              9 434
9 967        3 852       6 466              9 466
9 949        4 068       7 636              2 470

kto([9434, 9466, 2470], [9973, 9967, 9949]) возвращает [80779853376, 988939464559]: первое число и есть a · b. Три независимых маленьких умножения вместо одного большого, и их можно делать одновременно на трёх ядрах.

Сработало это потому, что произведение модулей - 988 939 464 559 - больше ответа. Убери третий модуль: M = 9973 · 9967 = 99 400 891, ответ в него не помещается, и сборка по двум остаткам вернёт первым числом 66 329 884. Это не a · b, а a · b mod M. Число верное по обоим модулям и неверное как произведение: остатки не знают, сколько полных оборотов по M сделал настоящий ответ.

Вторая граница - модули с общим делителем. x ≡ 1 (mod 4) и x ≡ 2 (mod 6) несовместны: первое требует нечётного числа, второе чётного. А x ≡ 1 (mod 4) и x ≡ 3 (mod 6) совместны, но решений до 24 два - 9 и 21: остатки определяют число только по модулю НОК(4, 6) = 12.

Что ломается без этого

Первое: результат больше M. Самая частая ошибка. Модулей набирают с запасом: их произведение должно превышать наибольший возможный ответ, а если ответ бывает отрицательным - удвоенный наибольший: собранные числа больше M / 2 тогда читают как отрицательные, x − M.

Второе: переполнение при сборке. Формула в лоб - rᵢ · Mᵢ · обратный - даёт слагаемые до M · mᵢ. Сначала приводят множитель по mᵢ, потом умножают на Mᵢ.

Третье: сравнение и деление в остатках. По двум наборам остатков нельзя сказать, какое число больше, и нельзя разделить одно на другое с округлением. Для этого число приходится собирать обратно.

Четвёртое: модули «на глаз». Модули 10 и 15 выглядят разными, но у них общий делитель 5. Проверка - алгоритм Евклида для каждой пары.

Зачем это в работе

Расшифровка RSA. Модуль ключа - произведение двух простых p и q. Вместо одной степени по модулю из 2048 бит считают две - по p и по q, каждая вдвое короче, - и собирают ответ китайской теоремой. Числа вдвое короче - умножение столбиком вчетверо дешевле, и показатели вдвое короче: по теореме Ферма показатель берут по модулю p − 1. Две такие степени стоят вчетверо меньше одной полной, и так устроена расшифровка в любой библиотеке.

Точные вычисления. Определитель матрицы из целых чисел или произведение многочленов с огромными коэффициентами считают по нескольким простым модулям, помещающимся в машинное слово, и собирают в конце. Вся работа идёт над короткими числами, длинное появляется один раз.

Расписания. Задача запускается на 1-й минуте и дальше каждые 4, вторая - на 2-й и дальше каждые 9. Они совпадут на 29-й минуте и потом каждые 36 минут - это второй пример из разбора.

Хеши. Два хеша строки по разным простым модулям - это один хеш по модулю их произведения. Поэтому в Рабине-Карпе пара небольших модулей даёт ту же редкость ложных срабатываний, что один большой, а произведения остаются в пределах типа.

Теперь сам

1. Найди число от 0 до 14 с остатком 1 по модулю 3 и остатком 4 по модулю 5. Построй выключатели.
2. Сколько разных чисел можно однозначно задать остатками по модулям 7, 11 и 13?
3. Есть ли решение у пары x ≡ 1 (mod 6) и x ≡ 2 (mod 4)?
4. Числа до миллиарда перемножают по частям. Хватит ли модулей 9973, 9967 и 9949?