5 / 14
— представление
w
NAF (
d
) = (
d
n
−
1
, . . . , d
0
)
;
— окно
w
∈
Z
+
.
Выход:
— результат скалярного умножения
dP
= (
x, y
)
,
x, y
∈
F
p
.
Эффективный алгоритм скалярного умножения точки
dP
,
d
∈
Z
,
P
∈
E
(
F
p
)
, на основе метода несовместной формы представления
скаляра c окном
w
приведен ниже:
begin
/* Предварительные вычисления */
1.
P
1
←
P
2.
P
2
←
dbl (
P
)
3.
foreach
(
i
= 3
,
5
, . . . ,
2
w
−
1
−
1)
{
4.
P
i
←
add (
P
i
−
2
, P
2
)
5.
}
/* Основные вычисления */
6.
Q
←
P
n
−
1
7.
while
(
i
≥
0)
{
8.
if
(
d
i
>
0)
{
9.
Q
←
da (
Q, P
d
i
)
10.
}
else
{
11.
if
(
d
i
<
0)
{
12.
Q
←
d
a
(
Q,
−
P
d
i
)
13.
}
else
{
14.
Q
←
dbl (
Q
)
15.
}
16.
}
17.
i
←
i
−
1
18.
}
19.
return
(
Q
)
end
Методы несовместной формы представления скаляра с окном,
использования композитных операций DBL, ADD, DA, использо-
вания свойств аффинной, Якоби и Якоби – Чудновского коорди-
натных систем. Утверждение 1.
Алгоритм
a
w
NAF
(алгоритм 1)
вычисления скалярного умножения точки
dP
,
d
∈
Z
,
P
∈
E
(
F
p
)
,
d
= (
d
n
−
1
, . . . , d
0
)
2
имеет среднюю вычислительную сложность
:
ˆ
L
a
w
NAF
(
n, w
) = I +
11
n
w
+ 1
+ 2
n
−
10 M+ 8
n
−
3
n
w
+ 1
−
8 S
,
w
— ширина окна предварительных вычислений. При этом потребу-
ется
2
w
−
2
−
1
предварительных вычислений точек. Вычислительная
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 69