7 / 14
структурой
2
J A −→ J
. Таким образом, ее вычислительная слож-
ность составит
13M + 5S
. Компромисс в использовании указанного
подхода зависит от мощности множества предварительно вычислен-
ных точек и количества необходимых сложений.
Если предварительно вычисленные точки конвертируются к аф-
финным координатам для алгоритма, то необходимо
(I+3 (2
w
−
2
−
2)M)
для расчета
Z
−
1
1
, Z
−
1
3
, . . . , Z
−
1
2
w
−
1
−
1
, используя групповой способ на-
хождений обратного элемента и
(3
∙
2
w
−
2
+ 2)M + (2
w
−
2
−
2) S
для
определения аффинной формы для каждого
P
i
=
X
i
Z
2
i
, Y
i
Z
−
3
i
. По-
сле того, как все предварительно вычисленные точки переведены в
аффинные координаты, на шаге
Q
←
2
Q P
k
i
выполняется операция
DA
со структурой
2
J A −→ J
, а на шаге
Q
←
2
Q P
k
i
— со
структурой
2
J A −→ J
. Шаг
Q
←
2
Q
осуществляется
2
A −→ J
в первый раз и
2
J −→ J
в остальных случаях. Последний шаг это
J −→ A
.
Если
d
i
6
= 0
, то
d
i
=
±
1
с вероятностью около
1
/
2
w
−
3
. Вы-
числительная сложность предварительных вычислений составляет
L
a
PreC
w
NAF
(
n, w
) = (3M+ 5S) + (8M+ 3S) + (2
w
−
2
−
2) (11M+ 3S) =
= (11
∙
2
w
−
2
−
11)M+ (3
∙
2
w
−
2
+ 2)
.
Приведение рассчитанных значений точек в аффинную фор-
му имеет вычислительную сложность, равную
L
a
PreC
w
NAF
(
n, w
) = I +
+ (6
∙
(2
w
−
2
−
1)
−
3)M+ (2
w
−
2
−
1) S
.
С предварительно вычисленными точками в форме Якоби – Чуднов-
ского остальная часть алгоритма имеет сложность
ˆ
L
a
w
NAF
(
n, w
) =
1
2
w
−
2
n
w
+1
−
1 (13M+5S) +
+
2
w
−
2
−
1
2
w
−
2
n
w
+1
−
1 (15M+7S) + (2M+4S) +
+
n
−
n
w
+1
−
1 (4M+4S) + (I+3M+S)
.
После приведения подобных слагаемых получим
ˆ
L
a
w
NAF
(
n, w
) = I +
1
2
w
−
2
n
w
+ 1
−
1 13 + 15 2
w
−
2
−
1 +
+ 2
n
−
n
w
+1
−
1 + 5 M+
1
2
w
−
2
n
w
+1
−
1 (5 + 7(2
w
−
2
−
1))+
+ 8
n
−
n
w
+ 1
−
1 +5 S
.
С предварительно вычисленными точками в аффинной форме,
остальная часть алгоритма имеет сложность
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 71