Участник:Кинжикеева Дина/ Алгоритм решения линейной системы сравнений

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

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

---

Введем некоторые определения.

Определение 1 Пусть m целое число большее единицы (m>1). Говорят, что a сравнимо с b по модулю m, если m делит (a-b) (обозначение: m|(a-b)), а именно выполняется равенство: a = b+tm, где t некоторое целое число. Сравнение записывает таким образом: [math] a ≡ b   (mod   m) [/math].

Определение 2 Число НОД(a,b) называется наибольшим общим делителем двух чисел a,b если:

1. 1. НОД(a,b) делит оба числа a и b;
   2. НОД(a,b) является наибольшим общим делителем чисел a и b, то если d|a и d|b, то d|НОД(a,b) (или, что то же самое, d меньше либо рано НОД(a,b)).

Определение 3 Числа a и b называются взаимно простыми, если НОД(a,b)=1.

Задана линейная система сравнений вида:

[math]x ≡ a_1  (mod   m_1) [/math]

[math]x ≡ a_2  (mod   m_2) [/math]

[math] ... [/math]

[math]x ≡ a_n  (mod   m_n)  , [/math]

где [math]  m_1,m_2,...,m_n [/math] - натуральные взаимно простые числа, [math]   a_1, a_2,..., a_n[/math] -некоторые целые числа.

Рассматривается задача решения линейной системы сравнений вида, описанного выше. Данная система сравнений имеет единственное решение по модулю [math]M=m_1m_2...m_n [/math] по китайской теореме об остатках. Эта теорема утверждает, что можно восстановить целое число по множеству его остатков от деления числа из некоторого набора попарно взаимно простых чисел. Теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы, предположительно датируемом третьим веком н. э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах» датируемой 1247 годом, где было приведено точное решение. Утверждение этой теоремы можно рассматривать как алгоритм решения линейной системы сравнений требуемого вида. Искомое решение ищется как сумма вида:

[math] x= ∑_{i=1}^{n} a_i M_i N_i   (mod   M)  , [/math]

где [math]M_i=M   /   m_i   , [/math] [math]N_i= M_{i}^{-1}  (mod   m_i) [/math].

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

Алгоритм строится на утверждении китайской теоремы об остатках.

Теорема. (Китайская теорема об остатках)

Пусть [math]m_1,m_2,...,m_n[/math] натуральные числа такие, что НОД([math]m_i,m_j[/math])=1, при [math]i≠j[/math] для любых [math]i,j=1,2,..,n[/math]. И пусть [math]a_1,a_2,...,a_n[/math] целые числа. Тогда система сравнений вида:

[math]x ≡ a_1  (mod   m_1) [/math]

[math]x ≡ a_2  (mod   m_2) [/math]

[math] ... [/math]

[math]x ≡ a_n  (mod   m_n)  , [/math]

имеет единственное решение по модулю числа [math]M=m_1m_2...m_n[/math]:

[math] x= ∑_{i=1}^{n} a_i M_i N_i   (mod   M)  (1), [/math]

где [math]M_i=M   /   m_i   , [/math] [math]N_i= M_{i}^{-1}  (mod   m_i) [/math].

Доказательство. Докажем существование решения, а именно, что решение [math]x[/math] удовлетворяет заданной системе сравнений. Рассмотрим [math]x   (mod   m_1)[/math]. Все слагаемые в сумме (1), кроме первого, делятся на [math]m_1[/math], а первое слагаемое [math]a_1M_1N_1 ≡ a_1   (mod   m_1)[/math], так как [math]M_1N_1≡1   (mod   m_1)[/math]. Таким образом, [math]x ≡ a_1  (mod   m_1) [/math]. Аналогичным образом для [math]m_2,..,m_n[/math]. Следовательно, [math]x[/math] -решение. Покажем единственность решения. Пусть существуют два различных решения системы [math]x_1[/math] и [math]x_2[/math].

[math]x_0=x_1-x_2[/math]

Тогда для любого [math]i=1,..,n[/math] [math]  m_i|x_0[/math], а следовательно и [math]M|x_0[/math] ([math]M|(x_1-x_2)[/math]). Это означает, что [math]x_1[/math] можно представить в виде: [math]x_1=x_2+kM[/math], [math]k[/math] некоторое целое число. Следовательно, [math]x_1=x_2   (mod   M)[/math], что и требовалось доказать. Теорема доказана.

Поэтапное описание алгоритма:

1. Вычисление значения [math]M[/math].

   [math]M=m_1m_2...m_n[/math]

2. Вычисление значений [math]M_i[/math], для всех [math]i=1,...,n[/math].

   [math]M_i=M/m_i[/math]

3. Нахождение обратных элементов к [math]M_i[/math] по соответствующему модулю при помощи алгоритма Евклида. Описание расширенного алгоритма Евклида:

   [math]a^{-1}  (mod   b) [/math]

   [math]t_0=a   t_1=b [/math]

   [math]t_0=t_1q_1+t_2[/math]

   [math]t_1=t_2q_2+t_3[/math]

   [math]...[/math]

   [math]t_{k-2}=t_{k-1}q_{k-1}+t_{k}   t_{k}=1 [/math]

   [math]t_{k-1}=t_{k}q_{k}[/math]

   [math]p_0=1   p_1=q_1[/math]

   [math]p_j=q_jp_{j-1}+p_{j-2}   j=2,...,k [/math]

   [math]a^{-1}=(-1)^{k+1}p_{k-1}[/math]

4. Формирование итогового ответа.

   [math] x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)[/math]

2 Литература

1. Применко Э.А. Алгебраические основы криптографии: Учебное пособие. M.:Книжный Дом "ЛИБРОКОМ",2013.-288с.
2. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
3. Переславцева О. Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках. — Вестник ТГУ, 2009. — № 4. — ISSN 1810-0198.