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


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

Несколько связанных утверждений известны под именем китайской теоремы об остатках. Эта теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы «Сунь Цзы Суань Цзин» (кит. упр. 孙子算经, пиньинь: 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_1r_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]

Примечания

Литература

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

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Китайская теорема об остатках" в других словарях:

  • китайская теорема об остатках — КТО — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации Синонимы КТО EN chinese remainder theoremCRT …   Справочник технического переводчика

  • КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ — пусть А ассоциативное и коммутативное кольцо с единицей и такая совокупность идеалов кольца А, что для любых тогда для любого набора элементов найдется элемент такой, что x=xi(mod a,), i=l, ..., п. В частном случае, когда А кольцо целых чисел 2,… …   Математическая энциклопедия

  • Сравнение по модулю — Сравнение[1] по модулю натурального числа n в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и… …   Википедия

  • Система счисления — Системы счисления в культуре Индо арабская система счисления Арабская Индийские Тамильская Бирманская Кхмерская Лаоская Монгольская Тайская Восточноазиатские системы счисления Китайская Японская Сучжоу Корейская Вьетнамская Счётные палочки… …   Википедия

  • Теория чисел — Теория чисел, или высшая арифметика раздел математики, изучающий целые числа и сходные объекты. В теории чисел в широком смысле рассматриваются как алгебраические, так и трансцендентные числа, а также функции различного происхождения, которые… …   Википедия

  • Атака по времени — В криптографии атака по времени это атака по сторонним каналам, в которой атакующий пытается скомпрометировать криптосистему с помощью анализа времени, затрачиваемого на исполнение криптографических алгоритмов. Каждая логическая операция требует… …   Википедия

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия

  • Алгоритм Фюрера — (англ. Fürer’s algorithm)  быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… …   Википедия

  • Криптосистема Рабина — – криптографический алгоритм с открытым ключом. Ее безопасность, как и у RSA, связана с трудностью разложения на множители. Безопасность схемы Рабина опирается на сложность поиска квадратных корней по модулю составного числа. Сложность этого… …   Википедия

  • Сравнение по модулю натурального числа — В теории чисел сравнение[уточнить] по модулю натурального числа n задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом… …   Википедия

Книги

Другие книги по запросу «Китайская теорема об остатках» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.