12 / 14
+ 1
−
6
2
w
−
(
−
1)
w
n
w
+
v
(
w
)
−
1 (15M+7S) + (2M+4S) +
+
n
−
n
w
+
v
(
w
)
−
1 (2M+8S) + (I+3M+S)
,
а при преобразовании в аффинную форму среднюю вычислительную
сложность —
ˆ
L
a
s
\
w
NAF
(
n, w
) =
n
w
+
v
(
w
)
−
1 (13M+5S) + (2M+4S) +
+
n
−
n
w
+
v
(
w
)
−
1 (2M+ 8S) + (I+3M+S) =
= I+
11
n
w
+
v
(
w
)
+2
n
−
10 + 8
n
−
3
n
w
+
v
(
w
)
−
8 S
.
I
Сравнительная оценка средней вычислительной сложности алго-
ритма Хенкерсона и предлагаемого алгоритма
a
s
\
w
NAF
вычисления
скалярного умножения точки на основе метода несовместной фор-
мы представления скаляра со скользящим окном
w
на подмножествах
эллиптических кривых
P
192
⊂
E
представлена в табл. 3 (рис. 3).
Таблица 3
Средняя вычислительная сложность предлагаемого алгоритма
a
s
\
w
N
AF
и алгоритма Хенкерсона,
P
192
⊂
E
w
Алгоритм Хенкерсона
ˆ
L
a
s
\
w
NAF
(
n
)
Предлагаемый алгоритм
ˆ
L
a
s
\
w
NAF
(
n
)
S
a
s
\
w
NAF
3
2I + 1129
,
3M+ 903
,
0S 2I + 843
,
3M+ 1400
,
0S
2
4
2I + 1114
,
6M+ 892
,
7S 2I + 776
,
3M+ 1418
,
3S
4
5
2I + 1164
,
9M+ 897
,
4S 2I + 705
,
3M+ 1437
,
6S
10
6
2I + 1304
,
1M+ 925
,
8S 2I + 662
,
8M+ 1449
,
2S
20
7
2I + 1652
,
1M+ 1004
,
0S 2I + 627
,
1M+ 1459
,
0S
42
Заключение.
Проанализирован метод несовместной формы пред-
ставления скаляра с окном
w
(
w
NAF
) и на его основе получен но-
вый более быстрый, чем
w
NAF
-алгоритм Хенкерсона скалярного
умножения точки эллиптической кривой
a
w
NAF
. Доказано утвер-
ждение относительно вычислительной сложности предложенного
алгоритма
a
w
NAF
. Для алгоритма
a
w
NAF
выполнено соотношение
S
(
a
w
NAF
) = 2
w
−
2
−
1
.
Новая, более низкая оценка получена за счет использования сле-
дующих операций:
2
A −→ J
с
;
A J
с
−→ J
с
;
J
с
J
с
−→ J
с
;
2
J J
с
−→ J
;
2
J A −→ J
;
2
J A −→ J
;
2
A −→ J
;
2
J −→ J
;
J −→ A
(
A
,
J
с
и
J
— представление точки в аффин-
ных, Якоби – Чудновского и Якоби координатных системах); свойств
76 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3