Page 314 - Hardware Implementation of Finite-Field Arithmetic

294 Cha pte r T e n

i
i
which is impossible as k’ is smaller than 2 , and k’P =− 2 P would
imply that k’ + 2 = 0, which is impossible.
i
The basic Algorithms 10.2 and 10.3 consist of t doubling function
calls and at most t adding function calls, where the order of magnitude
m
[Eq. (10.25)] of t is log q = mlog p if L = GF(p ). Both functions are
2 2
relatively complex [Eqs. (10.12), (10.13), (10.16), (10.17), (10.20),
(10.21)] and include divisions. For that reason numerous alternative
algorithms have been proposed. Some of them are briefly introduced
in the next section.
10.4.3 Some Alternative Methods

10.4.3.1 Nonadjacent Forms
Several strategies have been proposed for reducing the point-
multiplication computation time. One of them is based on the fact
that subtracting is as efficient as adding so that a signed-bit
representation of k can be considered. Then, among all the signed-bit
representations of k, a so-called nonadjacent form (NAF) is chosen
([HMV04]), that is an expression
+
0
k = k’ · 2 t’ − 1 + k’ · 2 t’ − 2 . . . + k’ · 2 (10.28)
t’ − 1 t’ − 2 0
where k’ ∈ { − 1, 0, 1}, the length t’ of the representation is at most one
i
more than the length t of the binary representation, and no two
consecutive signed bits are nonzero. The maximum number of adding
function calls will be about t/2 instead of t, and the average number
of adding function calls can be proven to be equal to t/3.
A generalization of the preceding idea consists of expressing k in
a nonbinary signed-digit base, for example,
+
k = k’’ · 2 t’’ − 1 + k’’ · 2 t’’ − 2 . . . + k’’ · 2 0
t’’ − 1 t’’ − 2 0
where k’’ is an odd natural belonging to the interval − 2 w − 1 < k’’ < 2 w − 1 ,
i i
the length t’’ of the representation is at most one more than the length
t of the binary representation, and the average density of nonzero
digits among all the representations of this type is 1/(w + 1). The set
w-1
of values {iP for i in 3, 5, . . . , 2 − 1} must be first computed. Then the
average number of adding function calls is equal to t/(w + 1). It is the
so-called window NAF method.
10.4.3.2 Projective Coordinates
The goal is to avoid divisions. Given two naturals c and d, a subset of
3
L can be associated to every element (x, y) of L :
2
c
(x, y) → {(X, Y, Z) | Z ≠ 0, X = xZ , Y = yZ } (10.29)
d
3
Conversely, an element (X, Y, Z) of L , with Z ≠ 0, corresponds the
2
element (x, y) of L and is defined by
x = X/Z c y = Y/Z (10.30)
d