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

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

2017-12-01T06:20:28Z

Кинжикеева Дина:

:Алгоритм: Алгоритм решения линейной системы сравнений.
:Исполнитель: Кинжикеева Дина.

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет определение для каждого числа <math>M_i=M/m_i</math> , <math>i=1,..., n</math>, обратного к нему числа по модулю <math>m_i</math> при помощи расширенного алгоритма Евклида.

=== Макроструктура алгоритма ===
В алгоритм последовательно входят следующие макроструктуры:
#Вычисление <math>M_i</math> как произведение всех <math>m_j</math> для всех <math>j≠i, j =1, ...,n </math>;
#Вычисление обратного числа к <math>M_i</math> по расширенному алгоритму Евклида;
#Суммирование произведений вида <math>a_i M_i N_i</math>, <math>i=1, ...,n </math>, по модулю <math>M</math>.

=== Схема реализации последовательного алгоритма ===
Общая схема реализации программы:
:<math>for   i:=0   to   n </math>
:::<math>M=M*m_i;</math>
:<math>for   i:=0   to   n </math>
:::<math>M_i=M/m_i;</math>
:::<math>M_{i}^{-1}=РасширенныйАлгоритмЕвклида(M_i,m_i);</math>
:::<math>x=x+a_i*M_i*M_{i}^{-1};</math>
:<math>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>3nlogk</math>, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>. Основная сложность приходится на расчет обратного элемента к <math>M_i</math> по модулю <math>m_i</math> по расширенному Алгоритму Евклида, т.к при работе алгоритма Евклида (не расширенного) совершается максимальное число шагов <math>log(max\{a,b\})</math>, когда подаются на вход числа <math>a</math> и <math>b</math> взаимно простые (по условию данной задачи рассматриваются только такие числа), и число шагов в расширенном алгоритме совпадает, то исходя из предложенной реализации расширенного Алгоритма Евклида сложность его работы составит <math>3logk</math>. Всего данный алгоритм будет отрабатывать <math>n</math> раз, следовательно сложность Алгоритм решения линейной системы сравнений составит <math>3nlogk</math>.

=== Информационный граф ===
Описание графа алгоримта. В графе алгоритма в яросно-параллельной форме выделяется 3 яруса (см. рис.1). '''Первый ярус''': расчет <math>M</math> и <math>M_i</math>. '''Второй ярус''': умножение вида <math>M_ia_i</math>. '''Третий ярус''': растчет <math>M_{i}^{-1}</math> по расширенному Алгоритму Евклида, и формирование итогового ответа как сумму <math>M_ia_iM_{i}^{-1}</math>. Во всех ярусах <math>i=1, ..., n</math>.

[[Файл:1.png|400px|thumb|center|рис.1 Информационный граф. Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).]]

Входные данные <math>m_i</math> подаются на первый ярус, <math>a_i</math> -на второй (см. рис.2).

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

=== Ресурс параллелизма алгоритма ===
Для реализации алгоритма решения линейной системы сравнений потребуется выполнить последовательно следующие ярусы:
*n раз первый ярус
*1 раз второй ярус
*<math>3*log(k)+n</math> раз третий ярус, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>.
Таким образом параллельная сложность алгоритма составит <math>3logk+2n+1</math>.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' <math>n</math> пар числе <math>(a_i, m_i)</math>, соответствующая линейному сравнению вида <math> x &equiv; a_i  (mod   m_i) </math> , где <math>m_i</math> - натуральные взаимно простые числа, <math> a_i</math> -некоторые целые числа, <math>i=1, ..., n</math>.

'''Объем входных данных:''' <math>2n</math>.

'''Выходные данные:''' число <math>x</math> - решение линейной системы сравнений.

'''Объем выходных данных:''' <math>1</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
Исследование масштабируемости проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Набор и границы значений изменяемых параметров запуска реализации алгоритма:

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

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

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

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

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Реализации данного алгоритма решения системы линейных сравнений на основе утверждения китайской теоремы об остатках не было найдено.

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

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

2017-11-30T23:11:13Z

Кинжикеева Дина:

:Алгоритм: Алгоритм решения линейной системы сравнений.
:Исполнитель: Кинжикеева Дина.

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет определение для каждого числа <math>M_i=M/m_i</math> , <math>i=1,..., n</math>, обратного к нему числа по модулю <math>m_i</math> при помощи расширенного алгоритма Евклида.

=== Макроструктура алгоритма ===
В алгоритм последовательно входят следующие макроструктуры:
#Вычисление <math>M_i</math> как произведение всех <math>m_j</math> для всех <math>j≠i, j =1, ...,n </math>;
#Вычисление обратного числа к <math>M_i</math> по расширенному алгоритму Евклида;
#Суммирование произведений вида <math>a_i M_i N_i</math>, <math>i=1, ...,n </math>, по модулю <math>M</math>.

=== Схема реализации последовательного алгоритма ===
Общая схема реализации программы:
:<math>for   i:=0   to   n </math>
:::<math>M=M*m_i;</math>
:<math>for   i:=0   to   n </math>
:::<math>M_i=M/m_i;</math>
:::<math>M_{i}^{-1}=РасширенныйАлгоритмЕвклида(M_i,m_i);</math>
:::<math>x=x+a_i*M_i*M_{i}^{-1};</math>
:<math>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>3nlogk</math>, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>. Основная сложность приходится на расчет обратного элемента к <math>M_i</math> по модулю <math>m_i</math> по расширенному Алгоритму Евклида, т.к при работе алгоритма Евклида (не расширенного) совершается максимальное число шагов <math>log(max\{a,b\})</math>, когда подаются на вход числа <math>a</math> и <math>b</math> взаимно простые (по условию данной задачи рассматриваются только такие числа), и число шагов в расширенном алгоритме совпадает, то исходя из предложенной реализации расширенного Алгоритма Евклида сложность его работы составит <math>3logk</math>. Всего данный алгоритм будет отрабатывать <math>n</math> раз, следовательно сложность Алгоритм решения линейной системы сравнений составит <math>3nlogk</math>.

=== Информационный граф ===
Описание графа алгоримта. В графе алгоритма в яросно-параллельной форме выделяется 3 яруса (см. рис.1). '''Первый ярус''': расчет <math>M</math> и <math>M_i</math>. '''Второй ярус''': умножение вида <math>M_ia_i</math>. '''Третий ярус''': растчет <math>M_{i}^{-1}</math> по расширенному Алгоритму Евклида, и формирование итогового ответа как сумму <math>M_ia_iM_{i}^{-1}</math>. Во всех ярусах <math>i=1, ..., n</math>.

[[Файл:1.png|400px|thumb|center|рис.1 Информационный граф. Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).]]

Входные данные <math>m_i</math> подаются на первый ярус, <math>a_i</math> -на второй (см. рис.2).

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

=== Ресурс параллелизма алгоритма ===
Для реализации алгоритма решения линейной системы сравнений потребуется выполнить последовательно следующие ярусы:
*n раз первый ярус
*1 раз второй ярус
*<math>3*log(k)+n</math> раз третий ярус, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>.
Таким образом параллельная сложность алгоритма составит <math>3logk+2n+1</math>.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' <math>n</math> пар числе <math>(a_i, m_i)</math>, соответствующая линейному сравнению вида <math> x &equiv; a_i  (mod   m_i) </math> , где <math>m_i</math> - натуральные взаимно простые числа, <math> a_i</math> -некоторые целые числа, <math>i=1, ..., n</math>.

'''Объем входных данных:''' <math>2n</math>.

'''Выходные данные:''' число <math>x</math> - решение линейной системы сравнений.

'''Объем выходных данных:''' <math>1</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

2017-11-30T23:01:40Z

Кинжикеева Дина:

:Алгоритм: Алгоритм решения линейной системы сравнений.
:Исполнитель: Кинжикеева Дина.

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет определение для каждого числа <math>M_i=M/m_i</math> , <math>i=1,..., n</math>, обратного к нему числа по модулю <math>m_i</math> при помощи расширенного алгоритма Евклида.

=== Макроструктура алгоритма ===
В алгоритм последовательно входят следующие макроструктуры:
#Вычисление <math>M_i</math> как произведение всех <math>m_j</math> для всех <math>j≠i, j =1, ...,n </math>;
#Вычисление обратного числа к <math>M_i</math> по расширенному алгоритму Евклида;
#Суммирование произведений вида <math>a_i M_i N_i</math>, <math>i=1, ...,n </math>, по модулю <math>M</math>.

=== Схема реализации последовательного алгоритма ===
Общая схема реализации программы:
:<math>for   i:=0   to   n </math>
:::<math>M=M*m_i;</math>
:<math>for   i:=0   to   n </math>
:::<math>M_i=M/m_i;</math>
:::<math>M_{i}^{-1}=РасширенныйАлгоритмЕвклида(M_i,m_i);</math>
:::<math>x=x+a_i*M_i*M_{i}^{-1};</math>
:<math>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>3nlogk</math>, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>. Основная сложность приходится на расчет обратного элемента к <math>M_i</math> по модулю <math>m_i</math> по расширенному Алгоритму Евклида, т.к при работе алгоритма Евклида (не расширенного) совершается максимальное число шагов <math>log(max\{a,b\})</math>, когда подаются на вход числа <math>a</math> и <math>b</math> взаимно простые (по условию данной задачи рассматриваются только такие числа), и число шагов в расширенном алгоритме совпадает, то исходя из предложенной реализации расширенного Алгоритма Евклида сложность его работы составит <math>3logk</math>. Всего данный алгоритм будет отрабатывать <math>n</math> раз, следовательно сложность Алгоритм решения линейной системы сравнений составит <math>3nlogk</math>.

=== Информационный граф ===
Описание графа алгоримта. В графе алгоритма в яросно-параллельной форме выделяется 3 яруса (см. рис.1). '''Первый ярус''': расчет <math>M</math> и <math>M_i</math>. '''Второй ярус''': умножение вида <math>M_ia_i</math>. '''Третий ярус''': растчет <math>M_{i}^{-1}</math> по расширенному Алгоритму Евклида, и формирование итогового ответа как сумму <math>M_ia_iM_{i}^{-1}</math>. Во всех ярусах <math>i=1, ..., n</math>.

[[Файл:1.png|400px|thumb|center|рис.1 Информационный граф. Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).]]

Входные данные <math>m_i</math> подаются на первый ярус, <math>a_i</math> -на второй (см. рис.2).

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

=== Ресурс параллелизма алгоритма ===
Для реализации алгоритма решения линейной системы сравнений потребуется выполнить последовательно следующие ярусы:
*1 раз первый ярус
*1 раз второй ярус
*<math>3*log(k)+1</math> раз третий ярус, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>.
Таким образом параллельная сложность алгоритма составит <math>3logk+2</math>.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' <math>n</math> пар числе <math>(a_i, m_i)</math>, соответствующая линейному сравнению вида <math> x &equiv; a_i  (mod   m_i) </math> , где <math>m_i</math> - натуральные взаимно простые числа, <math> a_i</math> -некоторые целые числа, <math>i=1, ..., n</math>.

'''Объем входных данных:''' <math>2n</math>.

'''Выходные данные:''' число <math>x</math> - решение линейной системы сравнений.

'''Объем выходных данных:''' <math>1</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

2017-11-30T22:12:54Z

Кинжикеева Дина:

:Алгоритм: Алгоритм решения линейной системы сравнений.
:Исполнитель: Кинжикеева Дина.

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет определение для каждого числа <math>M_i=M/m_i</math> , <math>i=1,..., n</math>, обратного к нему числа по модулю <math>m_i</math> при помощи расширенного алгоритма Евклида.

=== Макроструктура алгоритма ===
В алгоритм последовательно входят следующие макроструктуры:
#Вычисление <math>M_i</math> как произведение всех <math>m_j</math> для всех <math>j≠i, j =1, ...,n </math>;
#Вычисление обратного числа к <math>M_i</math> по расширенному алгоритму Евклида;
#Суммирование произведений вида <math>a_i M_i N_i</math>, <math>i=1, ...,n </math>, по модулю <math>M</math>.

=== Схема реализации последовательного алгоритма ===
Общая схема реализации программы:
:<math>for   i:=0   to   n </math>
:::<math>M=M*m_i;</math>
:<math>for   i:=0   to   n </math>
:::<math>M_i=M/m_i;</math>
:::<math>M_{i}^{-1}=РасширенныйАлгоритмЕвклида(M_i,m_i);</math>
:::<math>x=x+a_i*M_i*M_{i}^{-1};</math>
:<math>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>3nlogk</math>, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>. Основная сложность приходится на расчет обратного элемента к <math>M_i</math> по модулю <math>m_i</math> по расширенному Алгоритму Евклида, т.к при работе алгоритма Евклида (не расширенного) совершается максимальное число шагов <math>log(max\{a,b\})</math>, когда подаются на вход числа <math>a</math> и <math>b</math> взаимно простые (по условию данной задачи рассматриваются только такие числа), и число шагов в расширенном алгоритме совпадает, то исходя из предложенной реализации расширенного Алгоритма Евклида сложность его работы составит <math>3logk</math>. Всего данный алгоритм будет отрабатывать <math>n</math> раз, следовательно сложность Алгоритм решения линейной системы сравнений составит <math>3nlogk</math>.

=== Информационный граф ===
Описание графа алгоримта. В графе алгоритма в яросно-параллельной форме выделяется 3 яруса. '''Первый ярус''': расчет

[[Файл:1.png|400px|thumb|center|рис.1 Информационный граф. Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' <math>n</math> пар числе <math>(a_i, m_i)</math>, соответствующая линейному сравнению вида <math> x &equiv; a_i  (mod   m_i) </math> , где <math>m_i</math> - натуральные взаимно простые числа, <math> a_i</math> -некоторые целые числа, <math>i=1, ..., n</math>.
'''Объем входных данных:''' <math>2n</math>.
'''Выходные данные:''' число <math>x</math> - решение линейной системы сравнений.
'''Объем выходных данных:''' <math>1</math>.

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

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

2017-11-30T20:40:44Z

Кинжикеева Дина:

:Алгоритм: Алгоритм решения линейной системы сравнений.
:Исполнитель: Кинжикеева Дина.

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма составляет определение для каждого числа <math>M_i=M/m_i</math> , <math>i=1,..., n</math>, обратного к нему числа по модулю <math>m_i</math> при помощи расширенного алгоритма Евклида.

=== Макроструктура алгоритма ===
В алгоритм последовательно входят следующие макроструктуры:
#Вычисление <math>M_i</math> как произведение всех <math>m_j</math> для всех <math>j≠i, j =1, ...,n </math>;
#Вычисление обратного числа к <math>M_i</math> по расширенному алгоритму Евклида;
#Суммирование произведений вида <math>a_i M_i N_i</math>, <math>i=1, ...,n </math>, по модулю <math>M</math>.

=== Схема реализации последовательного алгоритма ===
Общая схема реализации программы:
:<math>for   i:=0   to   n </math>
:::<math>M=M*m_i;</math>
:<math>for   i:=0   to   n </math>
:::<math>M_i=M/m_i;</math>
:::<math>M_{i}^{-1}=РасширенныйАлгоритмЕвклида(M_i,m_i);</math>
:::<math>x=x+a_i*M_i*M_{i}^{-1};</math>
:<math>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>3nlogk</math>, где <math>k</math> равен максимальному значению <math>M_i</math>, <math>i=1, ...,n </math>. Основная сложность приходится на расчет обратного элемента к <math>M_i</math> по модулю <math>m_i</math> по расширенному Алгоритму Евклида, т.к при работе алгоритма Евклида (не расширенного) совершается максимальное число шагов <math>log(max\{a,b\})</math>, когда подаются на вход числа <math>a</math> и <math>b</math> взаимно простые (по условию данной задачи рассматриваются только такие числа), и число шагов в расширенном алгоритме совпадает, то исходя из предложенной реализации расширенного Алгоритма Евклида сложность его работы составит <math>3logk</math>. Всего данный алгоритм будет отрабатывать <math>n</math> раз, следовательно сложность Алгоритм решения линейной системы сравнений составит <math>3nlogk</math>.

=== Информационный граф ===
Опишем граф программы по

[[Файл:1.png|400px|thumb|center|рис.1 Информационный граф. Оранжевый- операция 1 (п. 1.2); желтый -операции 2 (п. 1.2); зеленый- операция умножения на ai ;синий-операции 3 (п. 1.2), голубой -операция 4 (п. 1.2).]]

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

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

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' <math>n</math> пар числе <math>(a_i, m_i)</math>, соответствующая линейному сравнению вида <math> x &equiv; a_i  (mod   m_i) </math> , где <math>m_i</math> - натуральные взаимно простые числа, <math> a_i</math> -некоторые целые числа, <math>i=1, ..., n</math>.
'''Объем входных данных:''' <math>2n</math>.
'''Выходные данные:''' число <math>x</math> - решение линейной системы сравнений.
'''Объем выходных данных:''' <math>1</math>.

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

Файл:1.png

2017-11-30T20:32:59Z

Кинжикеева Дина: Кинжикеева Дина загрузил новую версию Файл:1.png

Файл:2.png

2017-11-30T20:32:38Z

Кинжикеева Дина: Кинжикеева Дина загрузил новую версию Файл:2.png

Файл:2.png

2017-11-30T19:41:27Z

Кинжикеева Дина:

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

2017-11-30T18:54:27Z

Кинжикеева Дина:

Файл:1.png

2017-11-30T18:42:36Z

Кинжикеева Дина:

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

2017-11-30T17:48:12Z

Кинжикеева Дина:

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

2017-11-07T10:27:26Z

Кинжикеева Дина:

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

2017-11-07T10:26:22Z

Кинжикеева Дина:

Алгоритм: Алгоритм решения линейной системы сравнений.
Исполнитель: Кинжикеева Дина

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

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

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

2017-10-22T04:54:01Z

Кинжикеева Дина: /* Литература */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
----
Введем некоторые определения.

'''Определение 1''' Пусть ''m'' целое число большее единицы (''m''>1). Говорят, что ''a'' ''сравнимо'' с ''b'' по ''модулю'' ''m'', если ''m'' делит (''a''-''b'') (обозначение: ''m|(a-b)''), а именно выполняется равенство: ''a = b+tm'', где ''t'' некоторое целое число. Сравнение записывает таким образом: <math> a &equiv; 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>x &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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>.
=== Математическое описание алгоритма ===
Алгоритм строится на утверждении китайской теоремы об остатках.

'''Теорема.''' ''(Китайская теорема об остатках)''
:Пусть <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 &equiv; a_1  (mod   m_1) </math>
:<math>x &equiv; a_2  (mod   m_2) </math>
:<math> ... </math>
:<math>x &equiv; 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 &equiv; a_1   (mod   m_1)</math>, так как <math>M_1N_1&equiv;1   (mod   m_1)</math>. Таким образом, <math>x &equiv; 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>, что и требовалось доказать. Теорема доказана.

'''Поэтапное описание алгоритма:'''
#Вычисление значения <math>M</math>.
#:<math>M=m_1m_2...m_n</math>
#Вычисление значений <math>M_i</math>, для всех <math>i=1,...,n</math>.
#:<math>M_i=M/m_i</math>
#Нахождение обратных элементов к <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>
#Формирование итогового ответа.
#:<math> x=a_1 M_1 N_1+...+a_n M_n N_n   (mod   M)</math>

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

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

2017-10-22T04:41:41Z

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