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

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

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

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

[math]\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]m_1 \cdot m_2 \cdot \cdots \cdot m_n[/math].

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

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

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

[math]\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](m_i,m_j) = 1[/math] при всех [math]m_i ≠ m_j[/math] (т.е. попарно взаимно простые).

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

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

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

Шаг 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}= \frac1{M_i} \bmod{a_i}[/math] (например, используя расширенный алгоритм Евклида).

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

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

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

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

[math]r_1 = a + b(-q_0)[/math]

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

[math]\vdots[/math]

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

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

2 Литература

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