Китайская теорема об остатках | это... Что такое Китайская теорема об остатках? (original) (raw)

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

Содержание

1 Доказательства
2 Алгоритмы поиска решений
3 Вариации и обобщения
- 3.1 Формулировка для колец
4 Применения
5 Примечания
6 Литература
7 Ссылки

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

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

Воспользуемся методом математической индукции. При n = 1 утверждение теоремы очевидно. Пусть теорема справедлива при n = k - 1 , т. е. существует число , дающее остаток 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$ попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число , которое при делении на a_k даёт остаток r_k . В то же время при делении на $a_1, a_2, \dots, a_{k-1}$ число даёт остатки $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 взаимно просты, то делится на их произведение. ■

Конструктивный метод доказательства

Описанное ниже доказательство теоремы помогает решить практически важную задачу - поиск решения системы линейных уравнений по модулю.[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]

Покажем, что определенный таким образом является решением - проверим,что для него выполняется 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 убедимся, что , определенный формулой (2) является решением для (1).

В силу выбранного числа все числа ${x}^{'} \equiv x (\mathrm{mod}\, M)$ будут удовлетворять системе.

Покажем теперь, что среди чисел $0, 1, \dots , M - 1$ (множество ) не найдется другого решения кроме найденного нами ранее. Проведем доказательство этого факта от противного. Предположим, что получилось найти хотя бы два решения $(x_1, x_2 \in A)$ для некоторого набора остатков . Так как множество всех допустимых наборов $r_1, r_2, \dots , r_n$ является равномощным множеству , то для $\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)$ . Для такого найдется a_i такое, что $x \equiv r_1 \pmod{a_i}$ , $x \equiv r_2 \pmod{a_i}$ и r_1 ≠ r_2 противоречие.[5] ■

Замечания

Из доказанного выше, следует, что существует взаимно однозначное соответствие между вектором остатков из и числом из множества для любого набора $a_1, a_2, \dots , a_n$ , что означает, что отображение на заданное (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]

Алгоритмы поиска решений

Приведем ниже алгоритмы решения задачи, которая ставится в теореме - восстановление числа по набору его остатков от деления на некоторые заданные взаимно простые числа $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 из первого уравнения в третье с учетом выражения для получим $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 ≤< $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}\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]

Примечания

↑ Ишмухаметов, 2011, p. 36
↑ 1 2 Нестеренко, 2011, p. 19
↑ 1 2 Габидулин, 2011, p. 229
↑ Осипов Н.Н., 2008, p. 80
↑ 1 2 Осипов Н.Н., 2008, p. 19
↑ Габидудин, 2011, p. 230
↑ Шнаер, 2004, p. 249
↑ Габидудин, 2011, p. 229
↑ Нестеренко, 2011, p. 20
↑ Нестеренко, 2011, Теорема 2.4, p. 21
↑ Нестеренко, 2011, p. 22
↑ Переславцев, 2009, Вестник ТГУ, 2009. — № 4
↑ Шнаер, 2004, p. 250
↑ Ян Сонг Й, 2011, 8.4
↑ Модульное разделение секрета и системы электронного голосования
↑ R. Tolimieri FFT Algorithms
↑ Otmar Venjakob p-adic Numbers and the Hasse Principle
↑ Василенко, 2003, с. 130-131
↑ М. П. Минеев, В. Н. Чубариков об одном применении китайской теоремы об остатках к шифру Виженера (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)