6 / 14
сложность предварительных вычислений составит
(11
∙
2
w
−
2
−
11)M+
+ (3
∙
2
w
−
2
+ 2) S
.
J
Плотность несовместного представления с окном
w
(
w
NAF
)
скаляров длиной
n
примерно равна
n
w
+ 1
, где
n
∈
Z
+
— длина раз-
ложения скаляра
d
∈
Z
;
w
∈
Z
+
— ширина окна. Это означает, что
вычислительная сложность алгоритма
a
w
NAF
равна
ˆ
L
a
w
NAF
(
n, w
) = DBL + 2
w
−
2
−
1 ADD +
+
n
w
+ 1
−
1 ADD + (
n
−
1) DBL
.
Кроме того, необходима память для хранения
2
w
−
2
−
1
точек. В алго-
ритме
a
w
NAF
существует множество возможностей для использования
свойств координатных систем.
Рассмотрим возможности этапа предварительных вычислений то-
чек. Этот этап содержит большое количество сложений значений
2
P
,
результирующие значения затем используются в последующих вычи-
слениях. Это свидетельствует о том, что результат эффективнее хра-
нить в координатах Якоби – Чудновского. Существует два варианта по-
лучения значений
2
P
: значение может быть вычислено как
2
A −→ J
с
или как
2
A −→ A
. В первом случае каждое сложение в предваритель-
ных вычислениях будет иметь вид
J
с
J
с
−→ J
с
и вычислительную
сложность, равную
11M + 3S
. Если значение
2
P
сохранять в аффин-
ных координатах, то каждое сложение будет иметь вид
J
с
A −→ J
с
и вычислительную сложность, равную
8M+3S
. Компромисс заключа-
ется в том, что
2
A −→ A
имеет дорогостоящий шаг с нахождением
обратного элемента. Даже если предположить, что
I
<
30M
[3, 5–10],
то ширина окна
w
должна равняться, по меньшей мере, шести, для
большей эффективности. Поэтому примем, что для алгоритма шаг
P
2
←
2
P
имеет структуру
2
A −→ J
с
, а шаг
P
i
←
P
i
−
2
P
2
— струк-
туру
A J
с
−→ J
с
для
i
= 3
, и
J
с
J
с
−→ J
с
в остальных
случаях.
Для основного этапа вычислений потребуется
w
+ 1
удвоений и
сложений, поэтому координаты Якоби используются для временн ´ых
переменных. Если предварительно вычисленные значения хранятся в
координатах Якоби – Чудновского, то шаг
2
P Q
(для значений от-
личных от
±
1
) будет иметь структуру
2
J J
с
−→ J
. Сложность
такой операции составит
15M + 7S
. Еще одним важным дополнени-
ем к работе алгоритма является использование группового обратного
элемента для преобразования предварительно вычисленных значений
к аффинным координатам. Для этого применим метод Монтгомери
со сложностью вычислений
I + 3(
k
−
1)M
для
k
элементов поля
F
p
.
Преобразование предварительно вычисленных точек к аффинным ко-
ординатам позволит каждому сложению использовать операцию со
70 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3