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

2017-10-23T14:33:20Z

AnShchurova: Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Китайская теорема об ос…»

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Китайская теорема об остатках и алгоритм, построенный на её основе используется для решения линейной системы сравнений. Она утверждает, что система сравнений с попарно взаимно простыми модулями <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. Вычисляем <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'' целые.

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

Алговики - Вклад [ru]

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