Участник:Кинжикеева Дина/ Алгоритм решения линейной системы сравнений
- Алгоритм: Алгоритм решения линейной системы сравнений.
- Исполнитель: Кинжикеева Дина.
Свойства и структура алгоритма
Общее описание алгоритма
Введем некоторые определения.
Определение 1 Пусть m целое число большее единицы (m>1). Говорят, что a сравнимо с b по модулю m, если m делит (a-b) (обозначение: m|(a-b)), а именно выполняется равенство: a = b+tm, где t некоторое целое число. Сравнение записывает таким образом: [math]\displaystyle{ a ≡ b   (mod   m) }[/math].
Определение 2 Число НОД(a,b) называется наибольшим общим делителем двух чисел a,b если:
- НОД(a,b) делит оба числа a и b;
- НОД(a,b) является наибольшим общим делителем чисел a и b, то если d|a и d|b, то d|НОД(a,b) (или, что то же самое, d меньше либо равно НОД(a,b)).
Определение 3 Числа a и b называются взаимно простыми, если НОД(a,b)=1.
Задана линейная система сравнений вида:
- [math]\displaystyle{ x ≡ a_1  (mod   m_1) }[/math]
- [math]\displaystyle{ x ≡ a_2  (mod   m_2) }[/math]
- [math]\displaystyle{ ... }[/math]
- [math]\displaystyle{ x ≡ a_n  (mod   m_n)  , }[/math]
- где [math]\displaystyle{   m_1,m_2,...,m_n }[/math] - натуральные взаимно простые числа, [math]\displaystyle{   a_1, a_2,..., a_n }[/math] -некоторые целые числа.
Рассматривается задача решения линейной системы сравнений вида, описанного выше. Данная система сравнений имеет единственное решение по модулю [math]\displaystyle{ M=m_1m_2...m_n }[/math] по китайской теореме об остатках. Эта теорема утверждает, что можно восстановить целое число по множеству его остатков от деления числа из некоторого набора попарно взаимно простых чисел. Теорема в её арифметической формулировке была описана в трактате китайского математика Сунь Цзы, предположительно датируемом третьим веком н. э. и затем была обобщена Цинь Цзюшао в его книге «Математические рассуждения в 9 главах» датируемой 1247 годом, где было приведено точное решение. Утверждение этой теоремы можно рассматривать как алгоритм решения линейной системы сравнений требуемого вида. Искомое решение ищется как сумма вида:
- [math]\displaystyle{ x= ∑_{i=1}^{n} a_i M_i N_i   (mod   M)  , }[/math]
- где [math]\displaystyle{ M_i=M   /   m_i   , }[/math] [math]\displaystyle{ N_i= M_{i}^{-1}  (mod   m_i) }[/math].
Математическое описание алгоритма
Алгоритм строится на утверждении китайской теоремы об остатках.
Теорема. (Китайская теорема об остатках)
- Пусть [math]\displaystyle{ m_1,m_2,...,m_n }[/math] натуральные числа такие, что НОД([math]\displaystyle{ m_i,m_j }[/math])=1, при [math]\displaystyle{ i≠j }[/math] для любых [math]\displaystyle{ i,j=1,2,..,n }[/math]. И пусть [math]\displaystyle{ a_1,a_2,...,a_n }[/math] целые числа. Тогда система сравнений вида:
- [math]\displaystyle{ x ≡ a_1  (mod   m_1) }[/math]
- [math]\displaystyle{ x ≡ a_2  (mod   m_2) }[/math]
- [math]\displaystyle{ ... }[/math]
- [math]\displaystyle{ x ≡ a_n  (mod   m_n)  , }[/math]
- имеет единственное решение по модулю числа [math]\displaystyle{ M=m_1m_2...m_n }[/math]:
- [math]\displaystyle{ x= ∑_{i=1}^{n} a_i M_i N_i   (mod   M)  (1), }[/math]
- где [math]\displaystyle{ M_i=M   /   m_i   , }[/math] [math]\displaystyle{ N_i= M_{i}^{-1}  (mod   m_i) }[/math].
Доказательство. Докажем существование решения, а именно, что решение [math]\displaystyle{ x }[/math] удовлетворяет заданной системе сравнений. Рассмотрим [math]\displaystyle{ x   (mod   m_1) }[/math]. Все слагаемые в сумме (1), кроме первого, делятся на [math]\displaystyle{ m_1 }[/math], а первое слагаемое [math]\displaystyle{ a_1M_1N_1 ≡ a_1   (mod   m_1) }[/math], так как [math]\displaystyle{ M_1N_1≡1   (mod   m_1) }[/math]. Таким образом, [math]\displaystyle{ x ≡ a_1  (mod   m_1) }[/math]. Аналогичным образом для [math]\displaystyle{ m_2,..,m_n }[/math]. Следовательно, [math]\displaystyle{ x }[/math] -решение. Покажем единственность решения. Пусть существуют два различных решения системы [math]\displaystyle{ x_1 }[/math] и [math]\displaystyle{ x_2 }[/math].
- [math]\displaystyle{ x_0=x_1-x_2 }[/math]
Тогда для любого [math]\displaystyle{ i=1,..,n }[/math] [math]\displaystyle{   m_i|x_0 }[/math], а следовательно и [math]\displaystyle{ M|x_0 }[/math] ([math]\displaystyle{ M|(x_1-x_2) }[/math]). Это означает, что [math]\displaystyle{ x_1 }[/math] можно представить в виде: [math]\displaystyle{ x_1=x_2+kM }[/math], [math]\displaystyle{ k }[/math] некоторое целое число. Следовательно, [math]\displaystyle{ x_1=x_2   (mod   M) }[/math], что и требовалось доказать. Теорема доказана.
Поэтапное описание алгоритма:
- Вычисление значения [math]\displaystyle{ M }[/math].
- [math]\displaystyle{ M=m_1m_2...m_n }[/math]
- Вычисление значений [math]\displaystyle{ M_i }[/math], для всех [math]\displaystyle{ i=1,...,n }[/math].
- [math]\displaystyle{ M_i=M/m_i }[/math]
- Нахождение обратных элементов к [math]\displaystyle{ M_i }[/math] по соответствующему модулю при помощи алгоритма Евклида. Описание расширенного алгоритма Евклида:
- [math]\displaystyle{ a^{-1}  (mod   b) }[/math]
- [math]\displaystyle{ t_0=a   t_1=b }[/math]
- [math]\displaystyle{ t_0=t_1q_1+t_2 }[/math]
- [math]\displaystyle{ t_1=t_2q_2+t_3 }[/math]
- [math]\displaystyle{ ... }[/math]
- [math]\displaystyle{ t_{k-2}=t_{k-1}q_{k-1}+t_{k}   t_{k}=1 }[/math]
- [math]\displaystyle{ t_{k-1}=t_{k}q_{k} }[/math]
- [math]\displaystyle{ p_0=1   p_1=q_1 }[/math]
- [math]\displaystyle{ p_j=q_jp_{j-1}+p_{j-2}   j=2,...,k }[/math]
- [math]\displaystyle{ a^{-1}=(-1)^{k+1}p_{k-1} }[/math]
- Формирование итогового ответа.
- [math]\displaystyle{ x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M) }[/math]
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма составляет определение для каждого числа [math]\displaystyle{ M_i=M/m_i }[/math] , [math]\displaystyle{ i=1,..., n }[/math], обратного к нему числа по модулю [math]\displaystyle{ m_i }[/math] при помощи расширенного алгоритма Евклида.
Макроструктура алгоритма
В алгоритм последовательно входят следующие макроструктуры:
- Вычисление [math]\displaystyle{ M_i }[/math] как произведение всех [math]\displaystyle{ m_j }[/math] для всех [math]\displaystyle{ j≠i, j =1, ...,n }[/math];
- Вычисление обратного числа к [math]\displaystyle{ M_i }[/math] по расширенному алгоритму Евклида;
- Суммирование произведений вида [math]\displaystyle{ a_i M_i N_i }[/math], [math]\displaystyle{ i=1, ...,n }[/math], по модулю [math]\displaystyle{ M }[/math].
Схема реализации последовательного алгоритма
Общая схема реализации программы:
- [math]\displaystyle{ for   i:=0   to   n }[/math]
- [math]\displaystyle{ M=M*m_i; }[/math]
- [math]\displaystyle{ for   i:=0   to   n }[/math]
- [math]\displaystyle{ M_i=M/m_i; }[/math]
- [math]\displaystyle{ M_{i}^{-1}=РасширенныйАлгоритмЕвклида(M_i,m_i); }[/math]
- [math]\displaystyle{ x=x+a_i*M_i*M_{i}^{-1}; }[/math]
- [math]\displaystyle{ x=x  mod   M; }[/math]
Предлагаемая реализация Расширенного Алгоритма Евклида (С/С++):
- int inverse(int a, int m) {//a<m
- int c,cur=0, q,p0=0,p1=1,p2,m0=m;
- while (a) {
- cur++;
- c = m % a;
- q = (m-c)/a;
- p2 = q*p1+p0;
- p0 = p1;
- p1 = p2;
- m = a;
- a = c;
- }
- if (m==1) {
- if (cur%2)
- return p0;
- return m0-p0;
- }
- if (cur%2)
- return -1;
- }
Последовательная сложность алгоритма
Последовательная сложность алгоритма составляет [math]\displaystyle{ 3nlogk }[/math], где [math]\displaystyle{ k }[/math] равен максимальному значению [math]\displaystyle{ M_i }[/math], [math]\displaystyle{ i=1, ...,n }[/math]. Основная сложность приходится на расчет обратного элемента к [math]\displaystyle{ M_i }[/math] по модулю [math]\displaystyle{ m_i }[/math] по расширенному Алгоритму Евклида, т.к при работе алгоритма Евклида (не расширенного) совершается максимальное число шагов [math]\displaystyle{ log(max\{a,b\}) }[/math], когда подаются на вход числа [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] взаимно простые (по условию данной задачи рассматриваются только такие числа), и число шагов в расширенном алгоритме совпадает, то исходя из предложенной реализации расширенного Алгоритма Евклида сложность его работы составит [math]\displaystyle{ 3logk }[/math]. Всего данный алгоритм будет отрабатывать [math]\displaystyle{ n }[/math] раз, следовательно сложность Алгоритм решения линейной системы сравнений составит [math]\displaystyle{ 3nlogk }[/math].
Информационный граф
Описание графа алгоримта. В графе алгоритма в яросно-параллельной форме выделяется 3 яруса. Первый ярус: расчет
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Входные данные: [math]\displaystyle{ n }[/math] пар числе [math]\displaystyle{ (a_i, m_i) }[/math], соответствующая линейному сравнению вида [math]\displaystyle{ x ≡ a_i  (mod   m_i) }[/math] , где [math]\displaystyle{ m_i }[/math] - натуральные взаимно простые числа, [math]\displaystyle{ a_i }[/math] -некоторые целые числа, [math]\displaystyle{ i=1, ..., n }[/math]. Объем входных данных: [math]\displaystyle{ 2n }[/math]. Выходные данные: число [math]\displaystyle{ x }[/math] - решение линейной системы сравнений. Объем выходных данных: [math]\displaystyle{ 1 }[/math].
Литература
- Применко Э.А. Алгебраические основы криптографии: Учебное пособие. M.:Книжный Дом "ЛИБРОКОМ",2013.-288с.
- Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
- Переславцева О. Н. Распараллеливание алгоритмов с применением китайской теоремы об остатках. — Вестник ТГУ, 2009. — № 4. — ISSN 1810-0198.