Китайская теорема об остатках

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Несколько связанных утверждений известны под именем китайской теоремы об остатках. Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (кит. упр. 孙子算经, пиньинь: sunzi suanjing), предположительно датируемом третьим веком н. э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах» датируемой 1247 годом, где было приведено точное решение.[1]

Если натуральные числа a_1, a_2, \dots, a_n попарно взаимно просты, то для любых целых r_1, r_2, \dots, r_n таких, что 0 \leqslant r_i < a_i при всех i \in \{1, 2, \dots, n\}, найдётся число N, которое при делении на a_i даёт остаток r_i при всех i \in \{1, 2, \dots, n\}. Более того, если найдутся два таких числа N_1 и N_2, то N_1 \equiv N_2 \pmod{a_1\cdot a_2\cdot \ldots\cdot a_n}.


Доказательства[править | править вики-текст]

Метод математической индукции по n[править | править вики-текст]

Воспользуемся методом математической индукции. При n = 1 утверждение теоремы очевидно. Пусть теорема справедлива при n = k - 1, т. е. существует число M, дающее остаток r_i при делении на a_i при i \in \{1, 2, \dots, k - 1\}. Обозначим

d = a_1\cdot a_2\cdot\ldots\cdot a_{k-1}

и рассмотрим числа M, M + d, M + 2d, \dots, M + (a_k - 1)d. Покажем, что хотя бы одно из этих чисел даёт остаток r_k при делении на a_k. Допустим это не так. Поскольку количество чисел равно a_k, а возможных остатков при делении этих чисел на a_k может быть не более чем a_k - 1 (ведь ни одно число не даёт остаток r_k), то среди них найдутся два числа, имеющих равные остатки (принцип ящиков Дирихле). Пусть это числа M + sd и M + td при 0 \leqslant s < a_k, 0 \leqslant t < a_k и s \neq t. Тогда их разность (M + sd) - (M + td) = (s - t)d делится на a_k, что невозможно, т. к. 0 < |s - t| < a_k и d = a_1\cdot a_2 \cdot\ldots\cdot a_{k-1} взаимно просто с a_k, ибо числа a_1, a_2, \dots, a_k попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число N, которое при делении на a_k даёт остаток r_k. В то же время при делении на a_1, a_2, \dots, a_{k-1} число N даёт остатки r_1, r_2, \dots, r_{k-1} соответственно.

Докажем теперь, что N_1 \equiv N_2 \pmod{a_1\cdot a_2 \cdot\ldots\cdot a_n}. В самом деле N_1 \equiv N_2 \equiv r_i \pmod{a_i}, то есть N_1 - N_2 \equiv 0 \pmod{a_i}. Так как все a_i взаимно просты, то N_1 - N_2 делится на их произведение.


Конструктивный метод доказательства[править | править вики-текст]

Описанное ниже доказательство теоремы помогает решить практически важную задачу — поиск решения системы линейных уравнений по модулю.[2] Рассмотрим систему уравнений:


\begin{cases}
    x &\equiv r_1 \pmod{a_1} \\
    x &\equiv r_2 \pmod{a_2} \\
    &\vdots \\
    x &\equiv r_n \pmod{a_n} \\
\end{cases}
(1)

Если наборы (r_1, r_2, \dots, r_n) и (a_1, a_2, \dots, a_n) удовлетворяют условию теоремы, то решение системы (1) существует и единственно с точностью до операции взятия по модулю M, где M={\displaystyle\prod_{i=1}^n a_i}, причем справедлива формула[2][3][4]

x = \sum_{i=1}^n r_i M_i M_i^{-1}, где M_i = \frac M{a_i}, а M_i^{-1}= \frac1{M_i} \pmod{a_i}

(2)

Покажем, что определенный таким образом x является решением — проверим, что для него выполняется i-е равенство в системе[3]: x \equiv \sum_{j=1}^n r_j M_j M_j^{-1} \equiv r_i M_i M_i^{-1} \equiv r_i \pmod{a_i} Второе равенство справедливо т. к. M_j \equiv {\displaystyle\prod_{k \ne j}^n a_k} \equiv 0 \pmod{a_i} при всех i \ne j, третье т. к. M_i^{-1} является обратным для M_i по модулю a_i. Повторяя рассуждения для всех i, убедимся, что x, определенный формулой (2), является решением для (1).


В силу выбранного числа M все числа x' \equiv x \pmod M будут удовлетворять системе.


Покажем теперь, что среди чисел 0, 1, \dots, M - 1 (множество A) не найдется другого решения кроме найденного нами ранее. Проведем доказательство этого факта от противного. Предположим, что получилось найти хотя бы два решения x_1, x_2 \in A для некоторого набора остатков r. Так как множество B всех допустимых наборов (r_1, r_2, \dots, r_n) является равномощным множеству A, то для \overline A_x := A\setminus \{x_1, x_2\} и \overline B_r := B\setminus \{r\} выполнено |\overline A_x|<|\overline B_r|. Однако по доказанному ранее, для любого набора из \overline B_r существует решение из \overline A_x, следовательно по принципу Дирихле найдутся как минимум 2 набора остатков, которым соответствует одно и то же x \in A. Для такого x найдется a_i такое, что x \equiv r_1, x \equiv r_2 \pmod{a_i} и r_1 \ne r_2. Противоречие.[5]


Замечания[править | править вики-текст]

Из доказанного выше следует, что существует взаимно однозначное соответствие между вектором остатков из B и числом из множества A для любого набора (a_1, a_2, \dots, a_n), что означает, что отображение B в A, заданное (2), является биективным.[5]

Заметим, что кроме соответствия

(x \pmod{M})\leftrightarrow (r_1 \pmod{a_1}, r_2 \pmod{a_2}, \dots, r_n \pmod{a_n});

верны также[6][7]

(x_1 \pm x_2 \pmod{M})\leftrightarrow (r_{11} \pm r_{21}\pmod{a_1}, r_{12} \pm r_{22}\pmod{a_2}, \dots, r_{1n} \pm r_{2n}\pmod{a_n});

(x_1x_2\pmod{M})\leftrightarrow (r_{11}r_{21}\pmod{a_1}, r_{12}r_{22}\pmod{a_2}, \dots, r_{1n}r_{2n}\pmod{a_n});

Временная сложность перехода от вектора остатков к числу оценивается как O(k^2), где k — длина восстанавливаемого числа в битах.[8]

Алгоритмы поиска решений[править | править вики-текст]

Приведем ниже алгоритмы решения задачи, которая ставится в теореме — восстановление числа x по набору его остатков от деления на некоторые заданные взаимно простые числа a_1, a_2, \dots, a_n.

Элементарная алгебра[править | править вики-текст]

Как пример рассмотрим систему

 
\begin{cases}
    x \equiv 1 \pmod 2 \\
    x \equiv 2 \pmod 3 \\
    x \equiv 6 \pmod 7 \\
\end{cases}

Для решения системы выпишем отдельно решения первого, второго и третьего уравнений (достаточно выписать решения не превосходящие 2 × 3 × 7 = 42):

x_1 \in \{1, 3, 5, 7, 9, 11, \dots, 39, \mathbf{41}, 43, \dots\}
x_2 \in \{2, 5, 8, 11, 14, \dots, 38, \mathbf{41}, 44, \dots\}
x_3 \in \{6, 13, 20, 27, 34, \mathbf{41}, 48, \dots\}

Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю 42. В нашем случае x \in \{41, 83, 125, \dots\} или x \equiv 41 \pmod{42}.

Для того, чтобы продемонстрировать другой путь, переформулируем задачу. Найдем тройку чисел (u, v, w) таких, что:


\begin{cases}
    x = 1 + 2u \\
    x = 2 + 3v \\
    x = 6 + 7w \\
\end{cases}

Подставив x из первого уравнения во второе, получим 1 + 2u \equiv 2 \pmod 3, тогда 2u \equiv 1 \pmod 3, или u \equiv 1/2 \equiv 2 \pmod 3, или u = 2 + 3s;

подставив затем x из первого уравнения в третье с учетом выражения для u получим 1 + 2(2 + 3s) \equiv 6 \pmod 7 или 6s \equiv 1 \pmod 7, тогда s = 1/6 = 6 \pmod 7;

тогда x = 1 + 2(2 + 3 \cdot 6) = 41.

Алгоритм на основе китайской теоремы об остатках[править | править вики-текст]

Алгоритм сводится к поиску решений по формуле, данной в теореме[9].

Шаг 1. Вычисляем M={\displaystyle\prod_{i=1}^n a_i}.

Шаг 2. Для всех i\in \{1, 2, \dots, n\} находим M_i = \frac M{a_i}.

Шаг 3. Находим M_i^{-1}= \frac1{M_i} \bmod{a_i} (например, используя расширенный алгоритм Евклида).

Шаг 4. Вычисляем искомое значение по формуле x = \sum_{i=1}^n r_i M_i M_i^{-1} \mod M.

Алгоритм Гарнера[править | править вики-текст]

Рассмотрим набор модулей (a_1, a_2, \dots, a_n), удовлетворяющих условию теоремы. Другой теоремой из теории чисел утверждается, что любое число 0 \leqslant x < M = a_1\cdot a_2 \cdot\ldots\cdot a_n однозначно представимо в виде[10]

x = x_1 + x_2\cdot a_1 + x_3\cdot a_1\cdot a_2 + \dots + x_n\cdot a_1\cdot a_2\cdot\ldots\cdot a_{n-1}.

Вычислив по порядку все коэффициенты x_i для i \in \{1, 2, \dots, n\} мы сможем подставить их в формулу и найти искомое решение[11]:

Обозначим через r_{ij} = a_i^{-1} \bmod{a_j} и рассмотрим выражение для x по модулю a_i, где i\in \{2, \dots, n\}, получим:

x_1 = r_1;

r_2 = (x_1 + x_2a_1) \bmod{a_2};

x_2 = (r_2 - x_1)r_{12} \bmod{a_2};

r_3 = (x_1 + x_2a_1 + x_3a_1a_2) \bmod{a_3};

x_3 = ((r_3 - x_1)r_{13} - x_2)r_{23} \bmod{a_3}

и так далее.

Алгоритм нахождения коэффициентов x_i для наглядности продемонстрируем кодом в предположении, что массивы a, remainders и двумерный массив обратных элементов inverses уже инициализированы нужными значениями.

for (int i = 0; i < n; i++) {
	x[i] = remainders[i];
	for (int j = 0; j < i; j++) {
		x[i] = inverses[j][i] * (x[i] - x[j]);
		x[i] = x[i] % a[i];
		if (x[i] < 0)
			x[i] += a[i];
	}
}

Сложность вычисления коэффициентов x_i для данного алгоритма O(n^2). Такая же сложность и восстановления искомого числа по найденным коэффициентам.

Вариации и обобщения[править | править вики-текст]

Формулировка для колец[править | править вики-текст]

Пусть A, B_1, \dots, B_n — коммутативные кольца с единицей, \varphi_i\colon A \to B_iсюръективные гомоморфизмы, обладающие свойством \ker\varphi_i + \ker\varphi_j=A для всех i, j \in \{1,\dots,n\}, i \neq j. Тогда гомоморфизм

\Phi\colon A \to \prod_{i=1}^n B_i,

заданный формулой

\Phi(a) = (\varphi_1(a), \dots, \varphi_n(a)),

является сюръективным. Более того, \Phi определяет изоморфизм

A / \left(\bigcap_{i=1}^n \ker\varphi_i \right)\cong \prod_{i=1}^n B_i.


Если положить A = \mathbb Z/(a_1\cdot\ldots\cdot a_n\mathbb Z), B_i = \mathbb Z/a_i\mathbb{Z} \ (i = 1, 2, \dots, n; \ a_i \in \mathbb Z) и определить гомоморфизмы следующим образом

\varphi_i(x) = x \, \bmod{\,a_i},

то мы получим арифметическую версию теоремы.

Также часто встречается эквивалентная формулировка для колец, где B_i имеют форму A/I_i для некоторого набора идеалов I_1, \dots, I_n, гомоморфизмы \varphi_i являются естественными проекциями на A/I_i и требуется, чтобы I_i+I_j=A для любых i, j \in \{1, \dots, n\}, i \neq j. Другими словами, если идеалы I_1, \dots, I_n попарно взаимно просты (то есть сумма двух различных идеалов равна самому кольцу), то их произведение совпадает с их пересечением, и факторкольцо по этому произведению изоморфно произведению факторов:

A/(I_1I_2\ldots I_n) \cong A/I_1 \times A/I_2 \times \ldots \times A/I_n.

Применения[править | править вики-текст]

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

  • Взаимно однозначное соответствие между некоторым числом и набором его остатков, определяемым набором взаимно простых чисел, существование которого утверждается в теореме, на практике помогает работать не с длинными числами, а с наборами их коротких по длине остатков. Кроме того вычисления по каждому из модулей можно выполнять параллельно. [12]. Если в качестве базиса взять, к примеру, первые 500 простых чисел, длина каждого из которых не превосходит 12 бит, то этого хватит для представления десятичных чисел длиной до 1519 знаков. (Откуда взялось число 1519 понять очень просто: сумма десятичных логарифмов первых 500 простых чисел равна 1519,746…).
Например, в алгоритме RSA вычисления производятся по модулю очень большого числа n, представимого в виде произведения двух больших простых чисел. Теорема позволяет перейти к вычислениям по модулю этих простых делителей, которые по величине уже порядка корня из n, а значит имеют в два раза меньшую битовую длину. [13]
Отметим также, что применение вычислений согласно китайской теореме об остатках делает алгоритм RSA восприимчивым к атакам по времени[14]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • С. Ленг Алгебра. — М.: Мир, 1968. — С. 82—83.
  • Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — 262 с. — ISBN 5-7417-0377-9.
  • Н. Смарт Криптография. — 2005. — 528 с.
  • Осипов Н. Н. Теория чисел. — 2008. — С. 117.
  • Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — 190 с.
  • Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — 2011. — 202 с.
  • Переславцев О. Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках. — Вестник ТГУ, 2009. — № 4. — ISSN 1810-0198.
  • Фергюсон, Нильс, Шнаер, Брюс Практическая криптография. — М.: Вильямс, 2004. — 432 с. — ISBN 5-8459-0733-0.
  • Ян Сонг Й Криптоанализ RSA. — 2011. — 312 с. — ISBN 978-5-93972-873-7.
  • Шенец Н. Н. Модульное разделение секрета и системы электронного голосования. — Вестник БГУ, 2011. — № 1.
  • Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — 1000 экз. — ISBN 5-94057-103-4.

Ссылки[править | править вики-текст]