Page 322 - Hardware Implementation of Finite-Field Arithmetic

302 Cha pte r T e n

a = − 4μ + μ( − 4 − 0)/2 = − 6μ, b = (0 + 4)/2 = 2: r(3) = 0
a = 2 + μ( − 6μ− 0)/2 = − 1, b = (0 + 6μ)/2 = 3μ:
r(4) = 2 – (−1 – 6μ mod 4) = 1
a = 3μ + μ( − 1 − 1)/2 = 2μ , b = (1 + 1)/2 = 1: r(5) = 0
a = 1 + μ(2μ− 0)/2 = 2 , b = (0 − 2μ)/2 = − μ: r(6) = 0
a = − μ + μ(2 − 0)/2 = 0 , b = (0 − 2)/2 = − 1: r(7) = 0

a = − 1 + μ(0 − 0)/2 = − 1 , b = (0 − 0)/2 = 0:
r(8) = 2 – (−1 mod 4) = − 1
a = 0 + μ( − 1 + 1)/2 = 0 , b = ( − 1 + 1)/2 = 0

Thus,

4
8
17P = P + τ (P) − τ (P)
The following formal point-multiplication algorithms, in which
the function frobenius computes Eq. (10.54), are directly deduced from
[Eq. (10.65)]. In both cases it is assumed that the representation [Eq.
(10.65)] of kP has been previously computed.

Algorithm 10.6—Point multiplication (Q = kP), Koblitz curve, left to right
Q := point_at_infinity;
for i in 1 .. t loop
Q := frobenius(Q);
if r(t-i) = 1 then Q := Q+P;
elsif r(t-i) = -1 then Q := Q-P;
end if;
end loop;

Algorithm 10.7—Point multiplication (Q = kP), Koblitz curve, right to left
Q := point_at_infinity;
for i in 0 .. t-1 loop
if r(i) = 1 then Q := Q + P;
elsif r(i) = -1 then Q := Q-P;
end if;
P := frobenius(P);
end loop;
Comment 10.3 During the execution of step i > 0 of the preceding
algorithm and before the computation of Q + P or Q-P, the value of Q
is r τ i − 1 (P) + r τ i − 2 (P) + . . . + r τ(P) + r P and P has been substituted
i − 1 i − 2 1 0
i
i
by τ (P). If r τ i − 1 (P) + r τ i − 2 (P) + . . . + r τ(P) + r P = r τ (P), then
i − 1 i − 2 1 0 i
− r τ (P) + r τ i − 1 (P) + r τ i − 2 (P) + . . . + r τ(P) + r P =∞ (10.67)
i
i i − 1 i − 2 1 0