Русская Википедия:Китайская теорема об остатках

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Sun Tzu Chinese remainder theorem.svg
Исходная формулировка Сунь Цзы: Шаблон:Nowrap Шаблон:Nowrap Шаблон:Nowrap Шаблон:Nowrap Шаблон:Nowrap

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

История

Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (Шаблон:Китайский), предположительно датируемом III веком н. э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах», датируемой 1247 годом, где было приведено точное решениеШаблон:Sfn.

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

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

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

Индукция по числу уравнений

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

<math>d = a_1\cdot a_2\cdot\ldots\cdot a_{k-1}</math>.

Выберем произвольное число <math>a_k</math>, взаимно простое со всеми <math>a_1\dots a_{k-1}</math> и рассмотрим числа <math>M=\{m, m + d, m + 2d, \dots, m + (a_k - 1)\cdot d\}=\{m+t\cdot d\}_{0\leqslant t < a_k}</math>. Покажем, что все <math>t\in\{0,\dots,a_{k} - 1\}</math> являются остатками при делении каких-либо элементов из <math>M</math> на <math>a_k</math>.

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

Таким образом, среди рассматриваемых чисел найдётся число <math>N = m + t\cdot d</math>, которое при делении на <math>a_k</math> даёт остаток <math>r_k</math>. В то же время при делении на <math>a_1, a_2, \dots, a_{k-1}</math> число <math>N</math> даёт остатки <math>r_1, r_2, \dots, r_{k-1}</math> соответственно, так как <math>m + t\cdot d\equiv m \pmod{a_i}</math>.

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

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

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

<math>

\begin{cases} 

   x \equiv r_1 \pmod{a_1}, \\
   x \equiv r_2 \pmod{a_2}, \\
   \cdots\cdots\cdots\cdots\cdots\cdots \\
   x \equiv r_n \pmod{a_n}.\\

\end{cases} </math>

(1)

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

<math>x = \sum_{i=1}^n r_i M_i M_i^{-1}</math>, где <math>M_i = \frac M{a_i}</math>, а <math>M_i^{-1}</math> — мультипликативно обратный к <math>M_i \bmod a_i</math> элемент в кольце <math>\mathbb{Z}_{a_i}</math>.

(2)

Покажем, что определённый таким образом <math>x</math> является решением — проверим, что для него выполняется i-е равенство в системеШаблон:Sfn: <math>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}</math> Второе равенство справедливо так как <math>M_j \equiv {\displaystyle\prod_{k \ne j}^n a_k} \equiv 0 \pmod{a_i}</math> при всех <math>i \ne j</math>, третье так как <math>M_i^{-1}</math> является обратным для <math>M_i</math> по модулю <math>a_i</math>. Повторяя рассуждения для всех <math>i</math>, убедимся, что <math>x</math>, определённый формулой (2), является решением для (1).

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

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

Замечания

Из доказанного выше следует, что существует взаимно однозначное соответствие между вектором остатков из <math>B</math> и числом из множества <math>A</math> для любого набора <math>(a_1, a_2, \dots, a_n)</math>, т.е. отображение <math>B</math> в <math>A</math>, заданное (2), является биективнымШаблон:Sfn. Заметим, что кроме соответствия

<math>(x \pmod{M})\leftrightarrow (r_1 \pmod{a_1}, r_2 \pmod{a_2}, \dots, r_n \pmod{a_n}),</math>

верны такжеШаблон:SfnШаблон:Sfn

<math>(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})</math>,
<math>(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})</math>.

Вычислительная сложность перехода от вектора остатков к числу оценивается как <math>O(k^2)</math>, где k — длина восстанавливаемого числа в битахШаблон:Sfn.

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

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

Элементарная алгебра

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

<math>

\begin{cases} 

   x \equiv 1 \pmod 2, \\
   x \equiv 2 \pmod 3, \\
   x \equiv 6 \pmod 7. \\

\end{cases} </math>

Для решения системы выпишем отдельно решения первого, второго и третьего уравнений (достаточно выписать решения не превосходящие Шаблон:Nowrap):

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

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

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

<math>

\begin{cases} 

   x = 1 + 2u, \\
   x = 2 + 3v, \\
   x = 6 + 7w. \\

\end{cases} </math>

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

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

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

Алгоритм на основе китайской теоремы об остатках

Алгоритм сводится к поиску решений по формуле, данной в теоремеШаблон:Sfn.

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

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

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

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

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

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

<math>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}</math>.

Вычислив по порядку все коэффициенты <math>x_i</math> для <math>i \in \{1, 2, \dots, n\}</math> мы сможем подставить их в формулу и найти искомое решениеШаблон:Sfn:

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

<math>x_1 = r_1</math>;
<math>r_2 = (x_1 + x_2a_1) \bmod{a_2}</math>;
<math>x_2 = (r_2 - x_1)r_{12} \bmod{a_2}</math>;
<math>r_3 = (x_1 + x_2a_1 + x_3a_1a_2) \bmod{a_3}</math>;
<math>x_3 = ((r_3 - x_1)r_{13} - x_2)r_{23} \bmod{a_3}</math>
и так далее.

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

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

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

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

<math>\Phi\colon A \to \prod_{i=1}^n B_i</math>,

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

<math>\Phi(a) = (\varphi_1(a), \dots, \varphi_n(a))</math>,

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

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

Если положить <math>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)</math> и определить гомоморфизмы следующим образом

<math>\varphi_i(x) = x \, \bmod{\,a_i}</math>,

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

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

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

Кроме того существует обобщение на некоммутативные кольца без единиц с дополнительным условием, автоматически выполняющимся на кольцах с единицами.[1]

Также известно обобщение на решётки и коммутативные идемпотентные полукольца.[2]

Доказательство для евклидовых колец

Пусть <math>R</math> — евклидово кольцо и <math>m, n</math> — взаимно простые числа. Тогда докажем, что существует корректно заданный изоморфизм:

<math>R/_{(mn)} \cong R/_{(m)} \times R/_{(n)}</math>

Прямое отображение <math>[x]_{mn} \longrightarrow ([x]_m,\ [x]_n)</math> очевидно.

Для доказательства существования обратного отображения рассмотрим классы эквивалентности <math>[1]</math> и <math>[0]</math>:

<math>([1]_m,\ [0]_n) \longrightarrow [u]_{mn}</math>,

<math>([0]_m,\ [1]_n) \longrightarrow [v]_{mn}</math>.

Найдём <math>[u]_{mn}</math>, решив следующую систему уравнений:

<math>\begin{cases} 

u \equiv 1\ \pmod{m} \\
u \equiv 0\ \pmod{n}

\end{cases}</math>

<math>\exists y \in \mathbb{Z}:\ u = ny,\ ny \equiv 1 \pmod{m}</math>

Аналогично найдём <math>[v]_{mn}</math>:

<math>\exists x \in \mathbb{Z}:\ v = mx,\ mx \equiv 1 \pmod{n}</math>

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

<math>([a]_m,\ [b]_n) \longrightarrow [au + bv]_{mn},</math>

<math>au + bv \equiv a \pmod{m}</math>, так как <math>v \equiv 0 \pmod{m}</math> и <math>u \equiv 1 \pmod{m},</math>

<math>au + bv \equiv b \pmod{n}</math>, так как <math>u \equiv 0 \pmod{n}</math> и <math>v \equiv 1 \pmod{n}.</math>

Проверим корректность отображения, то есть что при взятии разных элементов из классов <math>[a]_m,\ [b]_n</math> результат не меняется:

<math> \begin{cases} 

a \equiv a' \pmod{m}, \\
b \equiv b' \pmod{n}.

\end{cases} </math>

Значит <math>au + bv \equiv a'u + b'v \pmod{mn},</math> отображение корректно.

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

Применения

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

  • Взаимно однозначное соответствие между некоторым числом и набором его остатков, определяемым набором взаимно простых чисел, существование которого утверждается в теореме, на практике помогает работать не с длинными числами, а с наборами их коротких по длине остатков. Кроме того, вычисления по каждому из модулей можно выполнять параллельноШаблон:Sfn. Если в качестве базиса взять, к примеру, первые 500 простых чисел, длина каждого из которых не превосходит 12 битов, то этого хватит для представления чисел длиной до 1519 десятичных знаков (сумма десятичных логарифмов первых 500 простых чисел равна 1519,746…). Например, в алгоритме RSA вычисления производятся по модулю большого числа n, представимого в виде произведения двух больших простых чисел. Теорема позволяет перейти к вычислениям по модулю этих простых делителей, которые по величине уже порядка корня из n, а значит имеют в два раза меньшую битовую длинуШаблон:Sfn. Отметим также, что применение вычислений согласно китайской теореме об остатках делает алгоритм RSA восприимчивым к атакам по времениШаблон:Sfn.
  • Такое представление числа под названием системы остаточных классов использовалось в ранних ЭВМ, особенно специализированных, т. к. позволяло выполнять арифметические операции над числами с большим числом битов путем параллельного вычисления операций над остатками. Так как модули можно было взять с небольшим числом битов, то таблицы операций над остатками по каждому модулю можно было просто запомнить в ПЗУ, как таблицу Пифагора, что позволяло производить арифметическую операцию практически за один такт.
  • На Теореме основаны схема Асмута — Блума и схема Миньотта — пороговые схемы разделения секрета в группе участников. Секрет могут узнать только k из n участников, объединив свои ключиШаблон:SfnШаблон:Sfn.
  • Одним из применений является быстрое преобразование Фурье на основе простых чисел[3].
  • Теорема лежит в основе принципа Хассе поиска целочисленных корней уравнения[4].
  • Теорема может быть использована при доказательстве свойства мультипликативности функции ЭйлераШаблон:Нет АИ.
  • На Теореме основывается алгоритм Полига — Хеллмана нахождения дискретного логарифма за полиномиальное время для чисел, имеющих специальный видШаблон:Sfn.
  • Теорема имеет множество применений в шифровании и дешифровании в криптографических системах, например, в криптосистеме Рабина или в шифре ВиженераШаблон:Sfn.
  • Реализация функций алгебры логики числовыми методамиШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:ВС

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ R. Tolimieri. FFT Algorithms Шаблон:Wayback.
  4. ↑ Otmar Venjakob p-adic Numbers and the Hasse Principle Шаблон:Wayback.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Китайская_теорема_об_остатках&oldid=10123969