Page 313 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 293

Observe that the order of (2,4) is equal to 4, that is, a divisor of the
order 8 of the group.

10.4.2 Basic Algorithms
Let (k , k , . . . , k ) be the binary representation of k, that is,
t − 1 t − 2 0
+
k = k · 2 t − 1 + k · 2 t − 2 . . . + k · 2 0 (10.24)
t − 1 t − 2 0
with

t ≅ log n ≅ log q (10.25)
2 2
Then kP can be computed according to the following scheme
([HMV04]):

kP = ( . . . 2(2(2∞+ k P) + k P) + . . . ) + k P (10.26)
t − 1 t − 2 0
The corresponding formal algorithm follows:
Algorithm 10.2—Point multiplication (Q = kP), left to right

Q := point_at_infinity;
for i in 1 .. t loop
Q := Q + Q;
if k(t-i) = 1 then Q := Q + P; end if;
end loop;
Comment 10.1 During the execution of step i > 1, and before the
conditional computation of Q + P, the value of Q is k’P where k’ = k t − 1 ·
+
1
2 i − 1 + k · 2 i − 2 . . . + k · 2 . If k is smaller than the order of P, then
t − 2 t − (i − 1)
k’P = P would imply that k’ = 1, which is impossible as k’ is even, and
k’P = − P would imply that k’ + 1 = 0, which is impossible.
Another computation scheme is ([HMV04])
2
kP = k P + k (2P) + k (2 P) + . . . + k (2 t − 1 P) (10.27)
0 1 2 t − 1
to which corresponds another formal algorithm:

Algorithm 10.3—Point multiplication (Q = kP), right to left
Q := point_at_infinity;
for i in 0 .. t-1 loop
if k(i) = 1 then Q := Q + P; end if;
P := P + P;
end loop;
Comment 10.2 During the execution of step i > 0, and before the
conditional computation of Q + P, the value of Q is k’P where k’ = k i − 1 ·
+
i
2 i − 1 + k · 2 i − 2 . . . + k · 2 and P has been substituted by 2 P. If k is
0
i − 2 0
i
smaller than the order of P, then k’P = 2 P would imply that k’ = 2 , i