Система Orphus

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

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

Если натуральные числа 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, что невозможно, приходим к противоречию.

Применения

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

  • Взаимно однозначное соответствие между некоторым числом и набором его остатков, определяемым набором взаимно простых чисел, существование которого утверждается в теореме, на практике помогает работать не с длинными числами, а с наборами их коротких по длине остатков. Кроме того вычисления по каждому из модулей можно выполнять параллельно. . Если в качестве базиса взять к примеру первые 500 простых чисел, длина каждого из которых не превосходит 12 бит, то этого хватит для представления десятичных чисел длины 1519 знаков. (Откуда взялось число 1519 понять очень просто: сумма десятичных логарифмов первых 500 простых чисел есть 1519.746…).

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

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

  • На теореме основаны Схема Асмута — Блума и Схема Миньотта пороговые схемы разделения секрета в группе участников - секрет могут узнать только k из n участников объединив свои ключи.
  • Одним из применения является быстрое преобразование Фурье на основе простых чисел
  • Теорема лежит в основе принципа Хассе поиска целочисленных корней уравнения.
  • Из теоремы следует мультипликативность функции Эйлера.
  • На теореме основывается Алгоритм Полига — Хеллмана нахождения дискретного логарифма за полиномиальное время для чисел имеющих специальный вид.
  • Теорема имеет множество применений в шифровании и дешифровании в криптографических системах, например, в криптосистеме Рабина или в шифре Виженера.

Система Orphus

Комментарии