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

Алгоритм: Алгоритм решения линейной системы сравнений.

Исполнитель: Кинжикеева Дина.

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

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

---

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

Определение 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 если:

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]\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], что и требовалось доказать. Теорема доказана.

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

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

   [math]\displaystyle{ M=m_1m_2...m_n }[/math]

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

   [math]\displaystyle{ M_i=M/m_i }[/math]

3. Нахождение обратных элементов к [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]

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

   [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] при помощи расширенного алгоритма Евклида.

Макроструктура алгоритма

В алгоритм последовательно входят следующие макроструктуры:

1. Вычисление [math]\displaystyle{ M_i }[/math] как произведение всех [math]\displaystyle{ m_j }[/math] для всех [math]\displaystyle{ j≠i, j =1, ...,n }[/math];
2. Вычисление обратного числа к [math]\displaystyle{ M_i }[/math] по расширенному алгоритму Евклида;
3. Суммирование произведений вида [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;

}

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 яруса (см. рис.1). Первый ярус: расчет [math]\displaystyle{ M }[/math] и [math]\displaystyle{ M_i }[/math]. Второй ярус: умножение вида [math]\displaystyle{ M_ia_i }[/math]. Третий ярус: растчет [math]\displaystyle{ M_{i}^{-1} }[/math] по расширенному Алгоритму Евклида, и формирование итогового ответа как сумму [math]\displaystyle{ M_ia_iM_{i}^{-1} }[/math]. Во всех ярусах [math]\displaystyle{ i=1, ..., n }[/math].

рис.1 Информационный граф. Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).

Входные данные [math]\displaystyle{ m_i }[/math] подаются на первый ярус, [math]\displaystyle{ a_i }[/math] -на второй (см. рис.2).

рис.2 Информационный граф с изображением входных данных.] Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).

Ресурс параллелизма алгоритма

Для реализации алгоритма решения линейной системы сравнений потребуется выполнить последовательно следующие ярусы:

• n раз первый ярус
• 1 раз второй ярус
• [math]\displaystyle{ 3*log(k)+n }[/math] раз третий ярус, где [math]\displaystyle{ k }[/math] равен максимальному значению [math]\displaystyle{ M_i }[/math], [math]\displaystyle{ i=1, ...,n }[/math].

Таким образом параллельная сложность алгоритма составит [math]\displaystyle{ 3logk+2n+1 }[/math].

Входные и выходные данные алгоритма

Входные данные: [math]\displaystyle{ n }[/math] пар числе [math]\displaystyle{ (a_i, m_i) }[/math], соответствующая линейному сравнению вида [math]\displaystyle{ x &equiv; a_i &#8194;(mod &#8194; 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].

Программная реализация алгоритма

Масштабируемость алгоритма и его реализации

Исследование масштабируемости проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• Число MPI процессов: [1:128] с шагом по степеням 2;
• Размер входа: [1000:10000000], число пар [math]\displaystyle{ (a_i,m_i) }[/math], задаваемых одно сравнение.

рис.3 График сильной масштабируемости. Диапазон[0:10000000]-число входных данных, диапазон[0:140]-число процессоров, диапазон[0:2000000000]-производительность.

рис.4 График слабой масштабируемости. Диапазон[0:10000000]-число входных данных, диапазон[0:140]-число процессоров, диапазон[0:1800000000]-производительность.

На основе параллельной реализации алгоритма производительность с ростом числа процессов увеличивается, а при приближении к числу процессов 64-128 , в зависимости от числа входных данных, начинает уменьшаться. Это объясняется использованием коллективных операций для расчета произведения всех модулей, по которым производятся вычисления, а также для формирования итогового ответа, а траты на коммуникационные обмены существенно возрастают с ростом числа использованных процессов. Ускорение производимых вычислений на каждом процессоре не компенсирует траты на коммуникационные обмены.

Существующие реализации алгоритма

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

Литература

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