Background Image
Previous Page  9 / 14 Next Page
Information
Show Menu
Previous Page 9 / 14 Next Page
Page Background

Рис. 2. Сравнение средней вычислительной сложности предлагаемого алгорит-

ма

a

w

NAF

(

1

) и алгоритма Хенкерсона (

2

) скалярного умножения точки на

подмножестве эллиптических кривых

P

192

E

,

w

= 3 , . . . , 7

Рассматриваемый метод имеет преимущество над

NAF

-методом,

поскольку в

NAF

-представлении целого не присутствует двух после-

довательных ненулевых значений. Поэтому для любых значений ши-

рины

w

из

NAF

-представления числа

d

, число представителей будет

принадлежать к интервалу

(

2

w

+1

/

3; 2

w

+1

/

3)

[3].

Выбор значения

w

определяет число точек, которые необходимо

предварительно рассчитать. Когда выбирается небольшая ширина окна

w

, то число точек, которые необходимо предварительно рассчитать,

приблизительно на треть больше, чем в

w

NAF

-методе с параметром

w

(2

w

+1

/

3 2

w

+1

/

4)

. Преимущество такого метода заключается в том,

что средняя плотность ненулевых чисел меньше, чем в

w

NAF

-методе.

Следовательно, количество сложений, необходимых для вычисления

скалярного умножения, уменьшается. Предлагаемый алгоритм

a

s

\

w

NAF

(алгоритм 2) основан на методе несовместной формы представления

скаляра со скользящим окном.

Алгоритм 2

. Эффективное вычисление скалярного умножения точ-

ки

dP

,

d

Z

,

P

E

(

F

p

)

на основе метода несовместной формы

представления скаляра

d

с окном

w

.

Вход:

— эллиптическая кривая

E

(

F

p

)

;

— точка

P

E

(

F

p

)

,

P

= (

x, y

)

,

x, y

F

p

;

— окно

w

;

— представление

w

NAF (

d

) = (

d

n

1

, . . . , d

0

)

.

Выход:

— результат скалярного умножения

dP

= (

x, y

)

,

x, y

F

p

.

Эффективный алгоритм скалярного умножения точки

dP

,

d

Z

,

P

E

(

F

p

)

, на основе метода несовместной формы представления

скаляра c окном приведен ниже:

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 73