8 / 14
ˆ
L
a
w
NAF
(
n, w
) =
n
w
+1
−
1 (13M+5S) + (2M+4S) +
+
n
−
n
w
+1
−
1 (2M+8S) + (I+3M+ S)
.
+ ˆ
L
a
w
NAF
(
n, w
) =I+
11
n
w
+1
+2
n
−
10 M+ 8
n
−
3
n
w
+1
−
8 S
.
I
В алгоритме 1 требуется такое же число промежуточных опера-
ций в простом поле
F
p
, что и при операциях нахождения обратного
элемента по умножению в простом поле. Для некоторых реализаций
это представляет собой проблему. Возможным решением может быть
сохранение промежуточных результатов в координатах
Z
2
,
Z
3
.
Для предложенного алгоритма
a
w
NAF
выполняется соотношение
S
(
a
w
NAF
) = 2
w
−
2
−
1
.
Сравнительная оценка вычислительной сложности алгоритма, по-
лученного Д. Хенкерсоном, и предлагаемого алгоритма
a
w
NAF
вычи-
сления скалярного умножения точки на основе метода несовместной
формы представления скаляра с шириной окна
w
при различных зна-
чениях ширины
w
на подмножестве эллиптических кривых
P
192
⊂
E
представлена в табл. 2 (рис. 2).
При увеличении ширины окна
w
вычислительные затраты основ-
ной части алгоритма сокращаются за счет их смещения на этап, свя-
занный с предварительными вычислениями.
Таблица 2
Средняя вычислительная сложность предлагаемого алгоритма
a
w
NAF
и алгоритма Хенкерсона,
P
192
⊂
E
w
Алгоритм Хенкерсона
ˆ
L
a
w
NAF
(
n
)
Предлагаемый алгоритм
ˆ
L
a
w
NAF
(
n
)
S
(
a
w
NAF
)
3
2I + 1155
,
0M+ 915
,
0S
2I + 902
,
0M+ 1384
,
0S
1
4
2I + 1112
,
2M+ 894
,
2S
2I + 796
,
0M+ 1412
,
0S
3
5
2I + 1129
,
0M+ 891
,
0S
2I + 726
,
0M+ 1432
,
0S
7
6
2I + 1228
,
4M+ 909
,
3S
2I + 675
,
7M+ 1445
,
7S
15
7
2I + 1473
,
0M+ 963
,
0S
2I + 638
,
0M+ 1456
,
0S
21
Алгоритм на основе метода несовместной формы представле-
ния скаляра со скользящим окном.
Метод несовместной формы
представления скаляра со скользящим окном основан на
w
NAF
-
представлении скаляра. Набор чисел представления по основанию 2
имеет вид
{−
2
w
−
1
+ 1
,
−
2
w
−
1
+ 3
, . . . ,
−
1
,
1
, . . . ,
2
w
−
1
−
3
,
2
w
−
1
−
1
}
.
Таким образом, будут вычислены точки
3
P
,
5
P
,. . . ,
(2
w
−
1
−
1)
P
.
72 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3