Участник:Kosean97/Метод встречи посередине в решении задачи дискретного логарифмирования в группе точек эллиптической кривой: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 22 промежуточные версии этого же участника)
Строка 61: Строка 61:
  
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
Если алгоритм использует в качестве составных частей другие алгоритмы, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде (т.е. на уровне арифметических операций), а давать только его макроструктуру, то здесь описывается структура и состав макроопераций. Если в других разделах описания данного алгоритма в рамках AlgoWiki используются введенные здесь макрооперации, то здесь даются пояснения, необходимые для однозначной интерпретации материала. Типичные варианты макроопераций, часто встречающиеся на практике: нахождение суммы элементов вектора, скалярное произведение векторов, умножение  матрицы на вектор, решение системы линейных уравнений малого порядка, сортировка, вычисление значения функции в некоторой точке, поиск минимального значения в массиве, транспонирование матрицы, вычисление обратной матрицы и многие другие.
+
Введем следующие макроопераций:
 +
*генерация случайной точки,
 +
*сравнение двух точек,
 +
*сортировка точек,
 +
*поиск точки в отсортированном массиве.
  
Описание макроструктуры очень полезно на практике. Параллельная структура алгоритмов может быть хорошо видна именно на макроуровне, в то время как максимально детальное отображение всех операций может сильно усложнить картину. Аналогичные аргументы касаются и многих вопросов реализации, и если для алгоритма эффективнее и/или технологичнее оставаться на макроуровне, оформив макровершину, например, в виде отдельной процедуры, то это и нужно отразить в данном разделе.
+
''Генерация случайной точки'' осуществляется случайным выбором натурального числа из множества <math>\{1, \dots, r\}</math> с последующим умножением на это число образующего элемента группы.<br>
Выбор макроопераций не однозначен, причем, выделяя различные макрооперации, можно делать акценты на различных свойствах алгоритмов. С этой точки зрения, в описании одного алгоритма может быть представлено несколько вариантов его макроструктуры, дающих дополнительную информацию о его структуре. На практике, подобные альтернативные формы представления макроструктуры алгоритма могут оказаться исключительно полезными для его эффективной реализации на различных вычислительных платформах.
+
Для определения ''сортировки'' и ''поиска'' определим операцию ''сравнения двух точек'' следующим образом:
 +
<math>\forall P_1, P_2 \in G \quad (P_1, P_2) \in Less \iff (P_1)_x < (P_2)_x</math>.<br>
 +
Под операцией ''сортировки'' будем понимать быструю сортировку, под операцией ''поиска'' - бинарный поиск. Каждая из операций использует описанную операцию ''сравнения''.
 +
 
 +
Макроструктура алгоритма представляет из себя последовательное выполнения операций генерации, сравнения и поиска точек.
  
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
Строка 106: Строка 114:
 
Будем считать генерацию точки за элементарную операцию.  
 
Будем считать генерацию точки за элементарную операцию.  
 
Сложность этапа генерации базы точек есть <math>\sqrt{r}</math>, так как точки хранятся в связном списке, добавление составляет константную сложность.
 
Сложность этапа генерации базы точек есть <math>\sqrt{r}</math>, так как точки хранятся в связном списке, добавление составляет константную сложность.
Сортировка производится алгоритмом Q-Sort, тем самым будет выполнено порядка <math>\sqrt{r}\log r</math> операций. Поиск по созданной базе точек осуществляется алгоритмом бинарного поиска, таким образом, проверка на вхождение нужного элемента производится за <math>\log r</math> операций.
+
Сортировка производится алгоритмом Q-Sort, тем самым будет выполнено порядка <math>\sqrt{r}\log r</math> операций. Поиск по созданной базе точек осуществляется алгоритмом бинарного поиска, таким образом, проверка на вхождение нужного элемента производится за <math>\log r</math> операций. Вычисление логарифма по найденной паре выполняется за
 +
константу.
 
<br><br>
 
<br><br>
 
Таким образом:
 
Таким образом:
* временная сложность алгоритма есть <math>\sqrt{r}\log r</math>,
+
* временная сложность алгоритма есть <math>O(\sqrt{r}\log r)</math>,
* оценка используемой памяти есть <math>\sqrt{r}</math>,
+
* оценка используемой памяти есть <math>O(\sqrt{r})</math>,
 
где <math>r</math> - это порядок группы <math>G</math> точек эллиптической кривой.
 
где <math>r</math> - это порядок группы <math>G</math> точек эллиптической кривой.
  
Строка 122: Строка 131:
  
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==
<!-- Здесь приводится оценка [[глоссарий#Параллельная сложность|''параллельной сложности'']] алгоритма: числа шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы и составом операций на ярусах.
+
В случае, когда квант точек, генерируемых за одну итерацию, достаточно велик, и за один подход генерируется вся база данных, мы имеем минимальную высоту ЯПФ. Число ярусов в таком случае равно семи (как следствие из Рис. 1). Не нарушая общности <math>q \in {\mathbb N}: q \cdot size = \sqrt{r}</math>, где <math>size</math> - число процессов.
 
 
Параллелизм в алгоритме часто имеет естественную иерархическую структуру. Этот факт очень полезен на практике, и его необходимо отразить в описании. Как правило, подобная иерархическая структура параллелизма хорошо отражается в последовательной реализации алгоритма через циклический профиль результирующей программы (конечно же, с учетом графа вызовов), поэтому циклический профиль ([[#Описание схемы реализации последовательного алгоритма|п.1.5]]) вполне  может быть использован и для отражения ресурса параллелизма.
 
 
 
Для описания ресурса параллелизма алгоритма (ресурса параллелизма информационного графа) необходимо указать ключевые параллельные ветви в терминах [[глоссарий#Конечный параллелизм|''конечного'']] и [[глоссарий#Массовый параллелизм|''массового'']] параллелизма. Далеко не всегда ресурс параллелизма выражается просто, например, через [[глоссарий#Кооодинатный параллелизм|''координатный параллелизм'']] или, что то же самое, через независимость итераций некоторых циклов (да-да-да, циклы - это понятие, возникающее лишь на этапе реализации, но здесь все так связано… В данном случае, координатный параллелизм означает, что информационно независимые вершины лежат на гиперплоскостях, перпендикулярных одной из координатных осей). С этой точки зрения, не менее важен и ресурс [[глоссарий#Скошенный параллелизм|''скошенного параллелизма'']]. В отличие от координатного параллелизма, скошенный параллелизм намного сложнее использовать на практике, но знать о нем необходимо, поскольку иногда других вариантов и не остается: нужно оценить потенциал алгоритма, и лишь после этого, взвесив все альтернативы, принимать решение о конкретной параллельной реализации. Хорошей иллюстрацией может служить алгоритм, структура которого показана на рис.2: координатного параллелизма нет, но есть параллелизм скошенный, использование которого снижает сложность алгоритма с <math>n\times m</math> в последовательном случае до <math>(n+m-1)</math> в параллельном варианте.
 
  
Рассмотрим алгоритмы, последовательная сложность которых уже оценивалась в [[#Последовательная сложность алгоритма|п.1.6]]. Параллельная сложность алгоритма суммирования элементов вектора сдваиванием равна <math>\log_2n</math>, причем число операций на каждом ярусе убывает с <math>n/2</math> до <math>1</math>. Параллельная сложность быстрого преобразования Фурье (базовый алгоритм Кули-Тьюки) для векторов с длиной, равной степени двойки - <math>\log_2n</math>. Параллельная сложность базового алгоритма разложения Холецкого (точечный вариант для плотной симметричной и положительно-определенной матрицы) это <math>n</math> шагов для вычислений квадратного корня, <math>(n-1)</math> шагов для операций деления и <math>(n-1)</math> шагов для операций умножения и сложения. -->
+
Анализируя ярусно-параллельную форма графа алгоритма, можно выделить:
 +
* 2 яруса ширины <math>\sqrt{r}</math>,
 +
* 5 ярусов ширины 1.
 +
Таким образом в терминах высоты ЯПФ сложность метода есть <math>O(1)</math>, в терминах ширины - <math>O(size)</math>
  
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
<!-- В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие. -->
+
'''Входные данные:''' <br>
 +
*<math>G</math> - группа точек эллиптической кривой, представленная простым числом, коэффициентами уравнения кривой, порядком группы,
 +
*<math>Q</math> - образующий элемент указанной группы,
 +
*<math>P</math> - элемент, логарифм которого необходимо найти.
 +
'''Выходные данные:''' <br>
 +
*<math>n</math> - число такое, что <math>nP=Q</math>.
  
 
== Свойства алгоритма ==
 
== Свойства алгоритма ==
  
 
= Программная реализация алгоритма =
 
= Программная реализация алгоритма =
=== Особенности реализации последовательного алгоритма ===
+
== Особенности реализации последовательного алгоритма ==
=== Локальность данных и вычислений ===
+
== Локальность данных и вычислений ==
=== Возможные способы и особенности параллельной реализации алгоритма ===
+
== Возможные способы и особенности параллельной реализации алгоритма ==
=== Масштабируемость алгоритма и его реализации ===
+
== Масштабируемость алгоритма и его реализации ==
=== Динамические характеристики и эффективность реализации алгоритма ===
+
[[file:dlog_perfomance.png|thumb|right|500px|Рис. 2. Масштабируемость метода встречи посередине в решении задачи дискретного логарифмирования в группе точек эллиптической кривой.]]
=== Выводы для классов архитектур ===
+
 
=== Существующие реализации алгоритма ===
+
=== Масштабируемость алгоритма ===
 +
В параллельном варианте описываемого метода, ось ординат разбивается между процессами на полусегменты равной длины, и каждому процессу, в зависимости от его номера, отводится свой полусегмент. Каждый процесс на этапе генерации базы данных, состоящей из точек на эллиптической кривой, определяет, какому процессу соответствует данная точка, и после того, как было создано некоторое количество точек, происходит пересылка каждого процесса с каждым. Взаимодействие осуществляется по принципу кругового турнира. <br>
 +
На этапе поиска коллизии происходит обмен точками по такому же принципу так, чтобы каждый процесс искал совпадение среди точек своего полусегмента.
 +
 
 +
=== Масштабируемость реализации ===
 +
Проведем исследование масштабируемости параллельной реализации алгоритма на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.<br>
 +
Используемый компилятор: icc version 15.0.0 (gcc version 4.4.7 compatibility). При компиляции используется оптимизация 2 уровня (флаг -O2).<br>
 +
Предложенная реализация написана на языке C++ с использованием библиотек STL, OpenSSL 1.1.1-dev и OpenMPI 1.10.2.
 +
 
 +
Параметризация задачи заключалась в указании:
 +
*числа задействованных процессов (2, 4, 8, 16, 32, 64, 128),
 +
*количества бит, необходимых для представления простого числа - параметра исследуемой группы (16, 20, 24, 28, 32, 36, 40).
 +
Каждое простое число генерировалось случайно и один раз. Для каждого простого числа коэффициенты эллиптической кривой генерировались случайно и один раз. При каждом запуске использовался один и тот же образующий элемент, и каждый раз логарифм считался для фиксированной точки. Количество точек, которые генерировались за одну итерацию, было выбрано так, чтобы 128 процессов завершили этап генерации базы данных точек за один подход.
 +
 
 +
На графике видно, что для групп меньшей мощности для достижения оптимального времени работы достаточно меньшего количества процессов. Для групп малого размера, накладные расходы, возникающие при синхронизации процессов, ведут к ухудшению производительности. По мере увеличения порядка группы, и увеличения тем самым количества точек для сортировки и поиска, увеличивается и количество процессов, необходимых для достижения оптимального времени работы алгоритма. Эта "диагональ" явно отображена в графической интерпретации проведенных экспериментов.
 +
 
 +
== Динамические характеристики и эффективность реализации алгоритма ==
 +
== Выводы для классов архитектур ==
 +
== Существующие реализации алгоритма ==
 +
В связи с тем, что данный метод имеет сугубо академический характер, широкоизвестных реализаций не существует. Главная проблема данного алгоритма заключается в том, что затраты по памяти составляют <math>\sqrt{|G|}</math>. В частности, если взять эллиптическую кривую наименьшего порядка из тех, что могли бы использоваться в приложениях, потребуется хранить в оперативной памяти вычислительного комплекса более чем терабайт данных.
  
 
= Литература =
 
= Литература =

Текущая версия на 01:26, 4 декабря 2017

Алгоритм: Применение метода встречи посередине в решении задачи дискретного логарифмирования в группе точек эллиптической кривой
Автор описания: Конюхов Сергей

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов[1] решения задачи дискретного логарифмирования. Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем и Виктором Миллером в 1985 году.

Содержание

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

Задача дискретного логарифмирования[2] в общем виде заключается в поиске решения [math]g^x=a[/math] в некоторой конечной абелевой группе [math]G[/math].

Мы же рассмотрим группу точек эллиптической кривой над полем [math]{\mathbb Z}_p[/math] характеристики [math]p \gt 3[/math]:

[math]E( {\mathbb Z}_p ) = {\mathcal O} \cup \{ (x, y) \in {\mathbb Z}_p^2 \enspace|\enspace y^2 \equiv x^3 + Ax + B \enspace (mod \thinspace p) \}[/math], где [math]A, B \in {\mathbb Z}_p[/math] - константы, удовлетворяющие условию [math]4A^3+27B^2 \ne 0 \enspace (mod \thinspace p)[/math].

В качестве группы [math]G[/math] возьмём циклическую подгруппу группы [math]E( {\mathbb Z}_p )[/math] порождённую элементом [math]Q[/math], то есть [math]G=\langle Q \rangle[/math].

Стоит отметить, что группа [math]G[/math] является аддитивной, и задачу DLOG стоит переформулировать: в уравнении [math]nQ=P[/math] требуется найти [math]n[/math].

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

Метод "встречи посередине"[3] является вероятностным и основан на так называемом парадоксе дней рождений - для того, чтобы при выборке с возвратом из множества мощности [math]r[/math] получить совпадение двух элементов с достаточно большой вероятностью, требуется произвести [math]\sqrt{r}[/math] попыток.

Eсли мы найдем совпадение точек вида: [math]lQ = kP[/math], то мы можем получить решение задачи как [math]n=lk^{-1}\enspace (mod \thinspace r)[/math].

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

[math]G = \langle Q \rangle[/math], [math]|G| = r[/math] - циклическая подгруппа группы точек эллиптической кривой. Уравнение [math]nQ = P[/math].

Дано: [math]E, Q, P, r[/math] - эллиптическая кривая, образующая группы [math]G[/math], логарифмируемый элемент, порядок группы.

Найти: [math]n[/math] - искомый логарифм.

Алгоритм:

  1. Случайно выбрать [math]\sqrt{r}[/math] чисел [math]l_i \in {\mathbb Z}_r[/math] и сохранить точки вида [math]l_iQ[/math].
  2. Отсортировать полученные на предыдущем этапе точки по координате [math]x[/math].
  3. Для случайных [math]k_j \in {\mathbb Z}_r[/math] вычислить точки [math]k_jP[/math] и осуществить поиск на совпадение в сохранённом массиве.
  4. В случае успеха вычислить [math]n=l_ik_j^{-1}\enspace (mod \thinspace r)[/math]. В случае провала перейти к пункту 3.

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

В описываемом алгоритме присутствует три вычислительных ядра: генерация базы данных, сортировка базы данных для дальнейшего поиска, генерация случайных точек - степеней изучаемой точки и поиск совпадений в созданной базе данных.

  1. Генерация базы данных.
    Выбирается некоторый "квант" - число точек - степеней образующей, которые будут генерироваться за одну итерацию. До тех пор пока не наберётся достаточное количество точек, генерируем "квант" случайных точек. Генерация точек осуществляется следующим образом: выбирается псевдослучайное число, после чего образующая умножается на него.
  2. Сортировка базы данных.
    Полученная база точек - степеней образующей сортируется по икс-координате (точка А больше точки Б, если икс-координата точки А больше икс-координаты точки Б). Алгоритм сортировки, например, быстрая сортировка.
  3. Генерация и поиск.
    Генерируется "квант" точек - степеней изучаемой точки. После чего производится поиск в базе данных точки, обладающую той же икс-координатой, что и выбранная. Поиск осуществляется, например, бинарным поиском.

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

Введем следующие макроопераций:

  • генерация случайной точки,
  • сравнение двух точек,
  • сортировка точек,
  • поиск точки в отсортированном массиве.

Генерация случайной точки осуществляется случайным выбором натурального числа из множества [math]\{1, \dots, r\}[/math] с последующим умножением на это число образующего элемента группы.
Для определения сортировки и поиска определим операцию сравнения двух точек следующим образом: [math]\forall P_1, P_2 \in G \quad (P_1, P_2) \in Less \iff (P_1)_x \lt (P_2)_x[/math].
Под операцией сортировки будем понимать быструю сортировку, под операцией поиска - бинарный поиск. Каждая из операций использует описанную операцию сравнения.

Макроструктура алгоритма представляет из себя последовательное выполнения операций генерации, сравнения и поиска точек.

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

В качестве описания схемы реализации последовательного алгоритма можно привести данный фрагмент программы на языке С++.

int main( int argc, char** argv )
{
     // Определяем группу, исследуемый элемент,
     // а так же объем базы данных точек и количество точек,
     // генерируемых за один раз, цель исследования.
     DLogConfig config( "config.txt" );
     DLogSolver solver( &argc, &argv, config );

     do
     {
          // Сгенерировать некоторое количество точек - степеней образующей.
          solver.GenerateDatabase();
     }
     // До тех пор, пока нужное количество точек не будет создано.
     while( !solver.DatabaseFull() );
     // Сортировка полученной базы данных.
     solver.PrepareDatabase();
     
     do
     {
          // Сгенерировать некоторое количество точек - степеней исследуемого элемента.
          solver.GeneratePoints();
          // Поиск совпадений в базе данных.
          solver.LookThrowDatabase();
     }
     // Повторять до тех пор, пока совпадение не будет найдено.
     while( !solver.SolutionFound() );
     // Вывести ответ.
     solver.PrintAnswer();

     return EXIT_SUCCESS;
}

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

Будем считать генерацию точки за элементарную операцию. Сложность этапа генерации базы точек есть [math]\sqrt{r}[/math], так как точки хранятся в связном списке, добавление составляет константную сложность. Сортировка производится алгоритмом Q-Sort, тем самым будет выполнено порядка [math]\sqrt{r}\log r[/math] операций. Поиск по созданной базе точек осуществляется алгоритмом бинарного поиска, таким образом, проверка на вхождение нужного элемента производится за [math]\log r[/math] операций. Вычисление логарифма по найденной паре выполняется за константу.

Таким образом:

  • временная сложность алгоритма есть [math]O(\sqrt{r}\log r)[/math],
  • оценка используемой памяти есть [math]O(\sqrt{r})[/math],

где [math]r[/math] - это порядок группы [math]G[/math] точек эллиптической кривой.

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

Рис.1. Информационная структура алгоритма дискретного логарифмирования методом встречи посередине.

На рисунке 1 можно видеть информационный граф алгоритма дискретного логарифмирования методом встречи посередине. Так, зеленым вершинам соответствует операция случайного выбора точки из группы. Каждая точка сохраняется в один из связных списков, группировка происходит на основании икс-координаты точки. Вершине, отмеченной розовым цветом, соответствует подсчёт общего количества точек. После этого, каждая группа точек по отдельности сортируется. Данному процессу соответствуют вершины, обозначенные красным цветом. Следующим этапом мы генерируем еще одно множество точек, и раздельно, в соответствии с икс-координатой, их сохраняем. Аналогично, этим операциям соответствуют зеленые и синие вершины (справа). В каждой группе из выбранных точек ищется вхождение соответствующего элемента в отсортированном массиве. Желтой вершине соответствует операция, результатом которой есть ответ на вопрос, была ли найдена коллизия.

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

В случае, когда квант точек, генерируемых за одну итерацию, достаточно велик, и за один подход генерируется вся база данных, мы имеем минимальную высоту ЯПФ. Число ярусов в таком случае равно семи (как следствие из Рис. 1). Не нарушая общности [math]q \in {\mathbb N}: q \cdot size = \sqrt{r}[/math], где [math]size[/math] - число процессов.

Анализируя ярусно-параллельную форма графа алгоритма, можно выделить:

  • 2 яруса ширины [math]\sqrt{r}[/math],
  • 5 ярусов ширины 1.

Таким образом в терминах высоты ЯПФ сложность метода есть [math]O(1)[/math], в терминах ширины - [math]O(size)[/math]

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

Входные данные:

  • [math]G[/math] - группа точек эллиптической кривой, представленная простым числом, коэффициентами уравнения кривой, порядком группы,
  • [math]Q[/math] - образующий элемент указанной группы,
  • [math]P[/math] - элемент, логарифм которого необходимо найти.

Выходные данные:

  • [math]n[/math] - число такое, что [math]nP=Q[/math].

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

Рис. 2. Масштабируемость метода встречи посередине в решении задачи дискретного логарифмирования в группе точек эллиптической кривой.

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

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

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

Проведем исследование масштабируемости параллельной реализации алгоритма на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.
Используемый компилятор: icc version 15.0.0 (gcc version 4.4.7 compatibility). При компиляции используется оптимизация 2 уровня (флаг -O2).
Предложенная реализация написана на языке C++ с использованием библиотек STL, OpenSSL 1.1.1-dev и OpenMPI 1.10.2.

Параметризация задачи заключалась в указании:

  • числа задействованных процессов (2, 4, 8, 16, 32, 64, 128),
  • количества бит, необходимых для представления простого числа - параметра исследуемой группы (16, 20, 24, 28, 32, 36, 40).

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

На графике видно, что для групп меньшей мощности для достижения оптимального времени работы достаточно меньшего количества процессов. Для групп малого размера, накладные расходы, возникающие при синхронизации процессов, ведут к ухудшению производительности. По мере увеличения порядка группы, и увеличения тем самым количества точек для сортировки и поиска, увеличивается и количество процессов, необходимых для достижения оптимального времени работы алгоритма. Эта "диагональ" явно отображена в графической интерпретации проведенных экспериментов.

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

В связи с тем, что данный метод имеет сугубо академический характер, широкоизвестных реализаций не существует. Главная проблема данного алгоритма заключается в том, что затраты по памяти составляют [math]\sqrt{|G|}[/math]. В частности, если взять эллиптическую кривую наименьшего порядка из тех, что могли бы использоваться в приложениях, потребуется хранить в оперативной памяти вычислительного комплекса более чем терабайт данных.

3 Литература

  1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. Изд. 2-е. доп. - М.: МЦНМО, 2006. - 336 с.
  2. Применко Э.А. Алгебраические основы криптографии: Учебное пособие. Изд. 2-е, испр. - М.: ЛЕНАНД, 2015. - 288 с.
  3. Бабенко Л.К., Ищукова Е.А., Сидоров И.Д. Параллельные алгоритмы для решения задач защиты информации. - М.: Горячая линия - Телеком, 2014. - 304 с.