Участник:AnShchurova/Китайская теорема об остатках

Свойства и структура алгоритма

Общее описание алгоритма

Китайская теорема об остатках и алгоритм, построенный на её основе используется для решения линейной системы сравнений. Она утверждает, что система сравнений с попарно взаимно простыми модулями [math]\displaystyle{ m_1, m_2, \ldots, m_n }[/math]:

[math]\displaystyle{ \begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \ldots \\ x \equiv a_n \pmod {m_n} \end{cases} }[/math]

всегда разрешима, и её решение единственно по модулю [math]\displaystyle{ m_1 \cdot m_2 \cdot \cdots \cdot m_n }[/math].

Задача, которая ставится в теореме — восстановление числа [math]\displaystyle{ x }[/math] по набору его остатков от деления на некоторые заданные взаимно простые числа [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math].

Формулировка теоремы:

Рассмотрим систему сравнений:

[math]\displaystyle{ \begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \ldots \\ x \equiv a_n \pmod {m_n} \end{cases} }[/math]

,где [math]\displaystyle{ (m_i,m_j) = 1 }[/math] при всех [math]\displaystyle{ m_i ≠ m_j }[/math] (т.е. попарно взаимно простые).

Положим [math]\displaystyle{ M = m_1\cdot \cdots \cdot m_k; M_i = M/m_i; i = 1, \dots , k }[/math]. Найдем (с помощью обобщенного алгоритма Евклида) числа [math]\displaystyle{ b_1, \dots , b_k }[/math] такие, что [math]\displaystyle{ M_i \cdot b_i \equiv 1 \bmod{m_i}; i = 1, \dots , k }[/math]. Тогда общее решение системы в целых числах имеет вид [math]\displaystyle{ x \equiv \sum_{i=1}^k M_i a_i b_i \bmod{M} ,т. е. x = \sum_{i=1}^k M_i a_i b_i + Mt }[/math], где [math]\displaystyle{ t ∈ Z }[/math].

Математическое описание алгоритма

Алгоритм на основе китайской теоремы об остатках (сводится к поиску решений по формуле, данной в теореме)

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

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

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

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

Здесь [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] и [math]\displaystyle{ m_1, m_2, \dots, m_n }[/math] попарно взаимно просты

Расширенный алгоритм Евклида:

Пусть [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — целые числа, не равные одновременно нулю

[math]\displaystyle{ r_1 = a + b(-q_0) }[/math]

[math]\displaystyle{ r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0) }[/math]

[math]\displaystyle{ \vdots }[/math]

НОД [math]\displaystyle{ (a,b) = r_n = as + bt }[/math]

Здесь s и t целые.

Литература

• Нестеренко А. Введение в современную криптографию Теоретико-числовые алгоритмы (2011)
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии (2003)
• Виноградов И. М. Основы теории чисел (1952)
• Н. Смарт. Криптография. (2005)