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

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

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

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

Метод математической индукции по n

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

$d = a_1 a_2\cdots 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 \leq s\leq a_k- 1$, $0 \leq t \leq a_k - 1$ и $s \neq t$. Тогда их разность $(M + sd) - (M + td) = (s - t)d$ делится на $a_{k}$, что невозможно, т. к. $0 < |s - t| < a_{k}$ и $d = a_1 a_2 \cdots 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 (\mathrm{mod}\, N)$. В самом деле $N_1 \equiv N_2 \equiv r_i (\mathrm{mod}\, a_i)$, то есть $N_1 - N_2 \equiv 0 (\mathrm{mod}\, 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} \\ \dots\\ 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) существует и единственно с точностью до операции взятия по модулю $(\mathrm{mod}\, 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}= \frac{1}{M_i} \pmod{a_i}$

(2)

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

В силу выбранного числа $M$ все числа ${x}^{'} \equiv x (\mathrm{mod}\, 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 \pmod{a_i}$, $x \equiv r_2 \pmod{a_i}$ и $r_1$ ≠ $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{r_2}, \dots, r_n \pmod{r_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{r_2}, \dots, {r}_{1n} \pm {r}_{2n}\pmod{r_n})$;

$(x_1*x_2\pmod{M})\leftrightarrow ({r}_{11}*{r}_{21}\pmod{a_1}, {r}_{12}*{r}_{22}\pmod{r_2}, \dots, {r}_{1n}*{r}_{2n}\pmod{r_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}$

Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю $(\mathrm{mod}\, 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 = 2 \pmod{3}$, тогда $2u = 1 \pmod{3}$, или $u = 1/2 \pmod{3} = 2 \pmod{3}$, или$u = 2 + 3s;$

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

Тогда $x = 1 + 2 *(2 + 3 * 6) = 41$;

Алгоритм на основе КТО

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

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

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

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

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

Алгоритм Гарнера

Рассмотрим набор модулей $i: a_1, a_2, \dots , a_n$, удовлетворяющих условию теоремы. Другой теоремой из теории чисел утверждается, что любое число 0 ≤$x$< $M={\displaystyle\prod_{i=1}^n a_i}$ однозначно представимо в виде^[10]:

$x := x_1 + {x_2}{a_1} + {x_3}{a_1}{a_2} + \dots + {x_n}{a_1}{a_2}\dots{a_n}$.

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

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

$x_1 = r_1$;

$r_2 = x_1 + {x_2}{a_1} \pmod {a_2}$;

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

$r_3 = x_1 + {x_2}{a_1} + {x_3}{a_1}{a_2} \pmod{a_3}$;

$x_3 = ((a_3 - x_1)r_{13} - x_2)r_{23} \pmod {a_3}$;

$\dots$

Алгоритм нахождения коэффициентов $x_1$ для наглядности продемонстрируем кодом в предположении, что массивы int[ ] a, int[ ] remainders и двумерный массив обратных элементов int[ ][ ] 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({k^2})$. Такая же сложность и восстановления искомого числа по найденным коэффициентам.

Вариации и обобщения

Формулировка для колец

Пусть $A, (B_i)_{i \in I}$ — коммутативные кольца с единицей, $\phi_i: A \to B_i$ сюръективные гомоморфизмы, обладающие свойством $\ker\,\phi_i + \ker\,\phi_j=A$ для всех $i,j \in I, i \neq j$. Тогда гомоморфизм

$\Phi: A \to \prod_{i \in I} B_i$, заданный формулой

$\Phi(a) = (\phi_i(a))_{i \in I}$ является сюръективным. Более того, $\Phi$ определяет изоморфизм

$A / (\cap_{i \in I} \ker\,\phi_i )\simeq \prod_{i \in I} B_i$.

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

$\phi_i(x) \equiv x\mod a_i$

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

Также часто встречается следующая эквивалентная формулировка для колец, где $B_i$ имеют форму $A/I_i$, $\phi_i$ являются естественными проекциями на $A/I_i$ и требуется, чтобы $I_i+I_j=A$ для любых $i, j \in I, i \neq j$.

Применения

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

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

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

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

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

Примечания

1. ↑ Ишмухаметов, 2011, p. 36
2. ↑ ^{1 2} Нестеренко, 2011, p. 19
3. ↑ ^{1 2} Габидулин, 2011, p. 229
4. ↑ Осипов Н.Н., 2008, p. 80
5. ↑ ^{1 2} Осипов Н.Н., 2008, p. 19
6. ↑ Габидудин, 2011, p. 230
7. ↑ Шнаер, 2004, p. 249
8. ↑ Габидудин, 2011, p. 229
9. ↑ Нестеренко, 2011, p. 20
10. ↑ Нестеренко, 2011, Теорема 2.4, p. 21
11. ↑ Нестеренко, 2011, p. 22
12. ↑ Переславцев, 2009, Вестник ТГУ, 2009. — № 4
13. ↑ Шнаер, 2004, p. 250
14. ↑ Ян Сонг Й, 2011, 8.4
15. ↑ Модульное разделение секрета и системы электронного голосования
16. ↑ R. Tolimieri FFT Algorithms
17. ↑ Otmar Venjakob p-adic Numbers and the Hasse Principle
18. ↑ Василенко, 2003, с. 130-131
19. ↑ М. П. Минеев, В. Н. Чубариков об одном применении китайской теоремы об остатках к шифру Виженера (2010)

Литература

• С. Ленг Алгебра. — М.: Мир, 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

Ссылки

• Осипов Н.Н., Теория чисел (2008)
• Шенец Н.Н.,Модульное разделение секрета и системы электронного голосования(2011)
• Ишухаметов Ш.Т.,Методы факторизации натуральных чисел(2011)
• Нестеренко , Введение в современную криптографию Теоретико-числовые алгоритмы (2011)
• М. П. Минеев, В. Н. Чубариков об одном применении китайской теоремы об остатках к шифру Виженера (2010)

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.