4 / 14
L
a
(
n
) =
L
i
min
(
n
)
,
при этом
L
i
min
= min
c
∈L
i
E
{
L
c
(
n
)
}
,
(1)
где
E
:
E
(
F
p
) :
y
2
=
x
3
+
ax
2
+
b
(mod
p
)
— множество эллиптических
кривых, утвержденных Национальным институтом стандартов и тех-
нологий (National Institute of Standards and Technology, NIST). Далее
рассмотрим подмножества кривых
E
:
P
192
,
P
224
,
P
256
,
P
384
и
P
521
.
В настоящей статье будут приведены алгоритмы, когда при выпол-
нении условия (1) выполняется соотношение
S
(
a
)
6
= 0
.
Описание основных операций в поле
F
p
и обозначение их вычи-
слительной сложности представлены в табл. 1 [4].
Таблица 1
Обозначение вычислительной сложности операций в простом поле
Операция
Описание
A
Сложение/вычитание (
a
ddition/subtraction) в поле
F
p
R
Приведение по модулю (
r
eduction)
p
S
Возведение в квадрат (
s
quaring) в поле
F
p
M
Умножение в поле (
m
ultiplication) в поле
F
p
I
Нахождение мультипликативного обратного элемента (
i
nversion)
в поле
F
p
Эффективные алгоритмы вычисления скалярного умножения
точки.
Перечислим полученные в процессе настоящего исследования
алгоритмы.
Алгоритм на основе метода несовместной формы представле-
ния скаляра c окном.
Предварительные вычисления повышают эффек-
тивность вычисления кратной точки. При
w
≥
2
несовместное пред-
ставление (
w
NAF
) целого
d
по основанию 2 имеет вид
d
=
m
−
1
X
i
=0
k
i
2
i
,
где
w
≥
2
,
k
i
это простое,
|
d
i
|
<
2
w
−
1
[3].
Преимуществом указанного метода является то, что число ненуле-
вых чисел и, следовательно, необходимых сложений в ходе вычисле-
ний невелико. Предлагаемый алгоритм
a
w
NAF
(алгоритм 1) скалярного
умножения точки для данного
w
NAF
-представления скаляра основан
на этом свойстве.
Алгоритм 1
. Эффективное вычисление скалярного умножения точ-
ки
dP
,
d
∈
Z
,
P
∈
E
(
F
p
)
,
w
NAF (
d
) = (
d
n
−
1
, . . . , d
0
)
на основе метода
несовместной формы представления скаляра
d
с окном
w
.
Вход:
— эллиптическая кривая
E
(
F
p
)
;
— точка
P
∈
E
(
F
p
)
,
P
= (
x, y
)
,
x, y
∈
F
p
;
68 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3