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

структурой

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