11 / 14
Методы несовместной форм представления скаляра со сколь-
зящим окном, использования композитных операций
DBL
,
ADD
,
DA
, использования свойств аффинных, Якоби и Якоби – Чуднов-
ского координатных систем. Утверждение 2.
Алгоритм
a
s
\
w
NAF
(алгоритм 2) вычисления скалярного умножения точки
dP
,
d
∈
Z
,
P
∈
E
(
F
p
)
,
d
= (
d
n
−
1
, . . . , d
0
)
2
,
имеет среднюю вычислительную
сложность
:
ˆ
L
a
s
\
w
NAF
(
n, w
) =I +
11
n
w
+
v
(
w
)
+2
n
−
10 M+ 8
n
−
3
n
w
+
v
(
w
)
−
8 S
,
где
w
—
ширина окна предварительных вычислений;
v
(
w
) =
4
3
−
(
−
1)
w
32
w
−
2
.
При этом потребуется
4
3
(2
w
−
2
−
1)
предварительных вычислений
точек. Вычислительная сложность предварительных вычислений со-
ставит
L
a
PreC
s
\
w
NAF
(
n, w
) = 11
∙
2
w
−
(
−
1)
w
3
−
11 M+ 3
∙
2
w
−
(
−
1)
w
3
+2 S
.
J
Согласно утверждению Хенкерсона [4], средняя длина последо-
вательности нулей между окнами шириной
w
равна
v
(
w
) =
4
3
−
(
−
1)
w
3
∙
2
w
−
2
,
а вычислительная сложность алгоритма предварительных вычисле-
ний —
L
a
PreC
s
\
w
NAF
(
n, w
) = DBL+
2
w
−
(
−
1)
w
3
−
1 ADD +
+
n
w
+
v
(
w
)
−
1 ADD + (
n
−
1) DBL
,
или
L
a
PreC
s
\
w
NAF
(
n, w
) = (3M+5S) + (8M+3S) +
2
w
−
(
−
1)
w
3
−
2 (11M+3S)
.
С учетом конвертации значений в аффинную форму вычислительная
сложность составит
L
a
PreC
s
\
w
NAF
(
n, w
) = I+ 6
2
w
−
(
−
1)
w
3
−
1
−
3 M+
2
w
−
(
−
1)
w
3
−
1 S
.
При сохранении предварительно вычисленных точек в координатах
Якоби – Чудновского, последующий этап алгоритма имеет среднюю
вычислительную сложность
ˆ
L
a
s
\
w
NAF
(
n, w
) =
6
2
w
−
(
−
1)
w
n
w
+
v
(
w
)
−
1 (13M+5S) +
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 75