3 / 14
Рис. 1. Архитектура преобразований на основе эллиптических кривых
Пусть
E
— множество рассматриваемых кривых
E
(
F
p
)
,
L
i
— мно-
жество алгоритмов вычисления преобразований на основе эллиптиче-
ских кривых уровня
i
математической иерархии. При
i
= 1
множество
алгоритмов
L
1
будем называть множеством
базовых алгоритмов
. То-
гда алгоритм
a
∈ L
i
,
i >
1
, получается композицией из
t
алгоритмов
множества
L
i
−
1
:
F
a
:
L
t
i
−
1
−→ L
i
.
Архитектура алгоритмов представляет собой математическую ие-
рархию. Множество алгоритмов всех уровней архитектуры обознача-
ется как
A
=
S
i
=1
,
5
L
i
.
Вычислительной (средней вычислительной) сложностью
алгорит-
ма
a
является функция
L
a
(
n
)
(
ˆ
L
a
(
n
)
), определяющая зависимость вре-
мени (среднего времени) работы алгоритма
a
от входного параметра
n
[3].
Введем функцию
S
(
a
)
,
a
∈ A
, определяющую объем дополни-
тельной памяти для хранения данных, которые связаны с предва-
рительными вычислениями, и необходимой для работы алгоритма
a
:
S
:
A −→
Z
+
. Тогда наиболее эффективным алгоритмом
a
∈ L
i
,
полученным композицией
F
a
, является такой алгоритм, что
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 67