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

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

Китайская теорема об остатках — несколько связанных утверждений о решении линейной системы сравнений.

История[править | править вики-текст]

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

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

Если натуральные числа попарно взаимно просты, то для любых целых таких, что при всех найдётся число , которое при делении на даёт остаток при всех . Более того, если найдутся два таких числа и , то .


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

Индукция по числу уравнений[править | править вики-текст]

Воспользуемся методом математической индукции. При утверждение теоремы очевидно. Пусть теорема справедлива при , т. е. существует число , дающее остаток при делении на при . Обозначим

и рассмотрим числа . Покажем, что хотя бы одно из этих чисел даёт остаток при делении на . Допустим это не так. Поскольку количество чисел равно , а возможных остатков при делении этих чисел на может быть не более чем (ведь ни одно число не даёт остаток ), то среди них найдутся два числа, имеющих равные остатки (принцип ящиков Дирихле). Пусть это числа и при , и . Тогда их разность делится на , что невозможно, т. к. и взаимно просто с , ибо числа попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число , которое при делении на даёт остаток . В то же время при делении на число даёт остатки соответственно.

Докажем теперь, что . В самом деле , то есть . Так как все взаимно просты, то делится на их произведение.


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

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

(1)

Если наборы и удовлетворяют условию теоремы, то решение системы (1) существует и единственно с точностью до операции взятия по модулю , где , причем справедлива формула[2][3][4]

, где , а

(2)

Покажем, что определенный таким образом является решением — проверим, что для него выполняется i-е равенство в системе[3]: Второе равенство справедливо т. к. при всех , третье т. к. является обратным для по модулю . Повторяя рассуждения для всех , убедимся, что , определенный формулой (2), является решением для (1).

В силу выбранного числа все числа будут удовлетворять системе.

Покажем теперь, что среди чисел (множество ) не найдется другого решения кроме найденного нами ранее. Проведем доказательство этого факта от противного. Предположим, что получилось найти хотя бы два решения для некоторого набора остатков . Так как множество всех допустимых наборов является равномощным множеству , то для и выполнено . Однако по доказанному ранее, для любого набора из существует решение из , следовательно по принципу Дирихле найдутся как минимум 2 набора остатков, которым соответствует одно и то же . Для такого найдется такое, что и . Противоречие.[5]


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

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

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

;

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

;

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

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

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

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

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

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

Очевидно, что множество решений системы будет пересечение представленных выше множеств. По утверждению теоремы решение существует и единственно с точностью до операции взятия по модулю 42. В нашем случае или

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

Подставив x из первого уравнения во второе, получим , тогда , или , или , или ;

подставив затем x из первого уравнения в третье с учетом выражения для получим или , тогда и следовательно ;

тогда .

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

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

Шаг 1. Вычисляем .

Шаг 2. Для всех находим .

Шаг 3. Находим (например, используя расширенный алгоритм Евклида).

Шаг 4. Вычисляем искомое значение по формуле .

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

Рассмотрим набор модулей , удовлетворяющих условию теоремы. Другой теоремой из теории чисел утверждается, что любое число однозначно представимо в виде[10]

.

Вычислив по порядку все коэффициенты для мы сможем подставить их в формулу и найти искомое решение[11]:

Обозначим через и рассмотрим выражение для по модулю , где , получим:

;

;

;

;

и так далее.

Алгоритм нахождения коэффициентов для наглядности продемонстрируем кодом в предположении, что массивы 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];
	}
}

Сложность вычисления коэффициентов для данного алгоритма . Такая же сложность и восстановления искомого числа по найденным коэффициентам.

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

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

Пусть  — коммутативные кольца с единицей, сюръективные гомоморфизмы, обладающие свойством для всех . Тогда гомоморфизм

,

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

,

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

.


Если положить и определить гомоморфизмы следующим образом

,

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

Также часто встречается эквивалентная формулировка для колец, где имеют форму для некоторого набора идеалов , гомоморфизмы являются естественными проекциями на и требуется, чтобы для любых . Другими словами, если идеалы попарно взаимно просты (то есть сумма двух различных идеалов равна самому кольцу), то их произведение совпадает с их пересечением, и факторкольцо по этому произведению изоморфно произведению факторов:

.

Доказательство для евклидовых колец[править | править вики-текст]

Пусть - евклидово кольцо и - взаимно простые числа. Тогда докажем, что существует корректно заданный изоморфизм:

Прямое отображение очевидно.

Для доказательства существования обратного отображения рассмотрим классы эквивалентности и .

Найдём , решив следующую систему уравнений:

Аналогично найдём :

Покажем, что в общем виде выполняется:

, так как и

, так как и

Проверим корректность отображения, т.е. что при взятии разных элементов из классов результат не меняется.

Значит , отображение корректно.

Проверим, что построенное отображение действительно обратное.

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

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

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

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

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

  • С. Ленг. Алгебра. — М.: Мир, 1968. — С. 82—83.
  • Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие. — М.: МФТИ, 2011. — 262 с. — ISBN 5-7417-0377-9.
  • Гольденберг А. Задача остатков (рус.) // В.О.Ф.Э.М.. — 1887. — № 35. — С. 247—253.
  • Н. Смарт. Криптография. — 2005. — 528 с.
  • Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 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.

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