Операция "Раздолбай"

Китайская теорема об остатках: доказательство, применение в защите информации

Формулировка

Если натуральные числа a_1,a_2,\ldots,a_n\in \mathbb{N} попарно взаимно просты, то

\forall r_1, r_2,\ldots, r_n\in\mathbb{Z}: 0\leqslant r_i\leqslant a_i
\exist N\in\mathbb{Z}:~r_i=N~\bmod~a_i~~i=1,\ldots, n

Более того, если найдутся два таких числа N_1 и N_2, то

N_1\equiv N_2~\bmod~(a_1\cdot\ldots\cdot a_n).

Доказательство

Воспользуемся методом математической индукции.

При n=1 утверждение теоремы очевидно.

Пусть теорема справедлива при n=k-1, т.е. существует число M, дающее остаток r_i при делении на a_i при i=1,\ldots,k-1.

Обозначим d=a_1\cdot\ldots\cdot a_{k-1}. И рассмотрим числа

M,M+d,M+2d,\ldots,M+(a_k-1)d.

Покажем, что хотя бы одно из этих чисел дает остаток r_k при делении на a_k. Допустим это не так. Поскольку количество чисел равно a_k, а возможных остатков при делении этих чисел на a_k может быть не более чем a_k-1, то среди них найдутся два разных числа, имеющих равные остатки. Пусть это числа M+sd и M+td при 0\leqslant s,t\leqslant a_k-1 и s\ne t. Тогда их разность должна делиться на a_k, что невозможно, приходим к противоречию.

Применения

Китайская теорема об остатках широко применяется в теории чисел, криптографии и других дисциплинах.

Например, в алгоритме RSA вычисления производятся по модулю очень большого числа n, представимого в виде произведения двух больших простых чисел. КТО позволяет перейти к вычислениям по модулю этих простых делителей которые по величине уже порядка корня из n, а значит имеют в два раза меньшую битовую длину.

Отметим также, что применение вычислений согласно КТО делает алгоритм RSA восприимчивым к атакам по времени


Система Orphus

Комментарии (показать)