Китайская теорема об остатках
Два циферблата вращаются вместе, один по модулю m, другой по модулю n, пока оба не покажут нужные остатки. Тогда загорается вся сетка.
x0
0123456
00
1
2
3
4
1 / 35
Нажмите «Пуск». Оба циферблата сдвигаются на единицу за шаг; каждое x попадает в клетку (x mod 5, x mod 7). Строка 3 — цель первого циферблата, столбец 4 — второго.
На что обратить внимание
- При gcd(m, n) = 1 счётчик проходит каждую клетку сетки m × n ровно один раз, поэтому для любой пары (a, b) есть ровно один x меньше m·n.
- Возьмите m и n с общим множителем, например 4 и 6: половина сетки недостижима, а у некоторых систем нет решения.
- Именно это использует RSA-CRT: вычисления отдельно по модулю p и по модулю q, затем склейка результатов. Примерно в 4 раза быстрее.