9 / 14
Рис. 2. Сравнение средней вычислительной сложности предлагаемого алгорит-
ма
a
w
NAF
(
1
) и алгоритма Хенкерсона (
2
) скалярного умножения точки на
подмножестве эллиптических кривых
P
192
⊂
E
,
w
= 3 , . . . , 7
Рассматриваемый метод имеет преимущество над
NAF
-методом,
поскольку в
NAF
-представлении целого не присутствует двух после-
довательных ненулевых значений. Поэтому для любых значений ши-
рины
w
из
NAF
-представления числа
d
, число представителей будет
принадлежать к интервалу
(
−
2
w
+1
/
3; 2
w
+1
/
3)
[3].
Выбор значения
w
определяет число точек, которые необходимо
предварительно рассчитать. Когда выбирается небольшая ширина окна
w
, то число точек, которые необходимо предварительно рассчитать,
приблизительно на треть больше, чем в
w
NAF
-методе с параметром
w
(2
w
+1
/
3 2
w
+1
/
4)
. Преимущество такого метода заключается в том,
что средняя плотность ненулевых чисел меньше, чем в
w
NAF
-методе.
Следовательно, количество сложений, необходимых для вычисления
скалярного умножения, уменьшается. Предлагаемый алгоритм
a
s
\
w
NAF
(алгоритм 2) основан на методе несовместной формы представления
скаляра со скользящим окном.
Алгоритм 2
. Эффективное вычисление скалярного умножения точ-
ки
dP
,
d
∈
Z
,
P
∈
E
(
F
p
)
на основе метода несовместной формы
представления скаляра
d
с окном
w
.
Вход:
— эллиптическая кривая
E
(
F
p
)
;
— точка
P
∈
E
(
F
p
)
,
P
= (
x, y
)
,
x, y
∈
F
p
;
— окно
w
;
— представление
w
NAF (
d
) = (
d
n
−
1
, . . . , d
0
)
.
Выход:
— результат скалярного умножения
dP
= (
x, y
)
,
x, y
∈
F
p
.
Эффективный алгоритм скалярного умножения точки
dP
,
d
∈
Z
,
P
∈
E
(
F
p
)
, на основе метода несовместной формы представления
скаляра c окном приведен ниже:
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 73