Дифференацильная атака - История изменений

Demiandr: /* Математическое описание алгоритма */

2021-11-04T13:14:13Z

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

← Предыдущая версия		Версия от 13:14, 4 ноября 2021
Строка 10:		Строка 10:

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	Пусть <math>~~ΔX=~~({~~ΔX_1~~}{~~ΔX_2~~}{~~ΔX_3~~}...{~~ΔX_3~~})</math>		Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей <math>Δfirst</math>, после чего определяется наиболее вероятная разница выходных шифртекстов <math>Δlast</math> на предпоследнем раунде <math>R-1</math>. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования.
	~~Задачей криптоаналитика~~ является ~~нахождение~~		Пусть <math>p</math> - вероятность дифференциальной характеристики <math>Δfirst→Δlast</math>, воздействущей на <math>b</math> бит результирующего шифртекста. Тогда атака проводится следующим образом:
	~~Пусть~~ <math>~~{p}~~</math> ~~- вероя~~		# Берется небольшая положительная константа <math>c</math> (обычно равная 2 или 3). Генерируется <math>c/p</math> пар текстов с входной разницей <math>Δfirst</math>;
			# Все данные пары текстов пропускаются через <math>R</math> раундов алгоритма шифрования, после чего получаются соответствующие шифртексты <math>Y_{R}</math>;
			# Для всех возможных значений <math>b</math> бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов <math>Y_{R}</math> данные тексты расшифровываются на всех возможных значениях <math>b</math> бит раундового ключа, в результате чего получаются значения <math>Y_{R-1}</math>;
			# Для каждой пары текстов путем их сложения находится своя разница <math>ΔY_{R-1}</math>. Далее значение <math>ΔY_{R-1}</math> сравнивается c <math>Δlast</math>. Если они совпадают, счетчик для данного <math>b</math> бит ключа увеличивается на 1.
			После такого полного перебора раундовым ключом является то значение <math>b</math> бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

Demiandr: /* Общее описание алгоритма */

2021-11-04T12:38:16Z

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

← Предыдущая версия		Версия от 12:38, 4 ноября 2021
Строка 6:		Строка 6:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).		Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
	Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю ~~{\displaystyle 2^{32}}~~2^{32}. Является статистической атакой. ~~Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х.~~ Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.		Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
	Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.		Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

Demiandr: /* Последовательная сложность алгоритма */

2021-11-04T12:20:05Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 12:20, 4 ноября 2021
Строка 63:		Строка 63:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит число пар текстов, данный алгоритм имеет линейную сложность.		Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>c</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит число пар текстов, данный алгоритм имеет линейную сложность.

	=== Информационный граф ===		=== Информационный граф ===

Demiandr: /* Ресурс параллелизма алгоритма */

2021-11-04T12:19:19Z

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

← Предыдущая версия		Версия от 12:19, 4 ноября 2021
Строка 76:		Строка 76:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:		Как видно из предыдущего пункта, обработка каждого текста из множества возможных текстов происходит независимо от других текстов. Таким образом, каждый процесс может шифровать и расшифровывать свою часть всего множества текстов, что даст большое ускорение работы алгоритма. Объединяя полученные результаты со всех процессов можно определить результирующие биты последнего раундового ключа.

	* по <math>n</math> ярусов умножений и сложений (в каждом из ~~ярусов — <math>n</math> операций).~~

	Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

	* по <math>n</math> ярусов умножений и сложений (в каждом из ~~ярусов — <math>m</math> операций)~~.

	~~При этом использование режима накопления требует совершения умножений~~ и ~~сложений в режиме двойной точности, а в параллельном варианте это означает~~, что ~~практически все промежуточные вычисления для выполнения~~ алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

	При классификации по высоте ЯПФ, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с линейной сложностью''. ~~При классификации по ширине ЯПФ его сложность также будет ''линейной''~~.

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

Demiandr: /* Последовательная сложность алгоритма */

2021-11-04T12:14:29Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 12:14, 4 ноября 2021
Строка 63:		Строка 63:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит ~~числе~~ пар текстов, данный алгоритм имеет линейную сложность.		Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит число пар текстов, данный алгоритм имеет линейную сложность.

	=== Информационный граф ===		=== Информационный граф ===

Demiandr в 12:13, 4 ноября 2021

2021-11-04T12:13:20Z

← Предыдущая версия		Версия от 12:13, 4 ноября 2021
Строка 67:		Строка 67:
	=== Информационный граф ===		=== Информационный граф ===

	~~Опишем~~ [[глоссарий#Граф алгоритма\|граф алгоритма]] как аналитически, так и в виде рисунка.		Рассмотрим [[глоссарий#Граф алгоритма\|граф алгоритма]] для обработки одного текста как аналитически, так и в виде рисунка.

	[[Файл:~~YeqAX~~.~~png~~\|~~500px~~\|~~thumb~~\|center\|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]		[[Файл:Graphdifferential.jpg\|обрамить\|центр\|Информационная схема работы алгоритма]]

	Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

	~~Естественно введённые координаты области таковы:~~		Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
	* <math>i</math> ~~— меняется в диапазоне от~~ <math>~~1</math> до <math>m~~</math>, ~~принимая все целочисленные значения;~~
	* <math>j</math> ~~— меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения~~.

	~~Аргументы операции следующие:~~
	*<math>a</math>:
	** при <math>~~j = 1~~</math> ~~константа <math>0.</math>;~~
	** при <math>j > 1</math> — результат срабатывания операции, ~~соответствующей вершине с координатами <math>i, j-1</math>;~~
	*<math>b</math> ~~— элемент ''входных данных''~~, ~~а именно~~ <math>a_{~~ij}</math>;~~
	*<math>c</math> - ~~элемент входных данных <math>x_{j~~}</math>;

	~~Результат срабатывания операции является:~~
	* при <math>~~j < n~~</math> ~~- ''промежуточным данным'' алгоритма;~~
	* при <math>j = n</math> - выходным данным.

	~~Описанный граф можно посмотреть на рисунке~~, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

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

2021-11-04T11:31:07Z

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

@@ Строка 127: / Строка 127: @@
 ==== Масштабируемость алгоритма ====
 ==== Масштабируемость реализации алгоритма ====
 === Динамические характеристики и эффективность реализации алгоритма ===

Demiandr: /* Последовательная сложность алгоритма */

2021-11-04T11:30:24Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 11:30, 4 ноября 2021
Строка 63:		Строка 63:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

	Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.		Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

	=== Информационный граф ===		=== Информационный граф ===

Demiandr: Новая страница: «{{level-a}} == Свойства и структура алгоритма == === Общее описание алгоритма === Дифференциальн...»

2021-11-04T10:45:58Z

Новая страница: «{{level-a}} == Свойства и структура алгоритма == === Общее описание алгоритма === Дифференциальн...»

Новая страница

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

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

Как уже определено в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть сложность алгоритма составляет большое количество операций шифрования определенных значений текстов.

=== Схема реализации последовательного алгоритма ===

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

=== Информационный граф ===

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

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

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

При классификации по высоте ЯПФ, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

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

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]