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

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

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

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

$\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}$

всегда разрешима, и её решение единственно по модулю $m_1 \cdot m_2 \cdot \cdots \cdot m_n$.

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

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

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

$\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}$

,где $(m_i,m_j) = 1$ при всех $m_i ≠ m_j$ (т.е. попарно взаимно простые).

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

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

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

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

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

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

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

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

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

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

$r_1 = a + b(-q_0)$

$r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)$

$\vdots$

НОД $(a,b) = r_n = as + bt$

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

2 Литература

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