Page 321 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 301

Equation (10.57) defines a kind of integer division of α by τ, that is,
α = α’τ + r with r ∈ {−1, 0, 1} (10.62)
By repeatedly using the preceding relations, an expression of α
can be computed:
α = α τ + r
1 0
α = α τ + r (10.63)
1 2 1
. . .

α = α τ + r
t − 1 t t − 1
with r ∈ { − 1, 0, 1}. Thus (multiply the second equation by τ, the third
i
2
one by τ , and so on, and sum up the t equations)
t
α = r + r τ+ . . . + r τ t − 1 + α τ (10.64)
0 1 t − 1 t
It can be demonstrated that after a finite number of steps, t,
α = 0.
t
Consider the particular case where a = k and b = 0, that is, α(P) =
kP. Then, according to Eq. (10.64) with α = 0,
t
kP = r τ t − 1 (P) + r τ t − 2 (P) + . . . + r τ(P) + r P with
t − 1 t − 2 1 0
k ∈ { −1, 0, 1} (10.65)
i
The following algorithm computes this τ-ary representation of k.

Algorithm 10.5—s-ary representation of k
a := k; b := 0; i := 0;
while a /= 0 or b /= 0 loop
if a mod 2 = 0 then r(i) := 0;
else r(i) := 2 – ((a – 2*b) mod 4); end if;
old_a := a;
a := b + mu*(old_a – r(i))/2; b := (r(i) – old_a)/2;
i := i+1;
end loop;

Regarding the maximum value of t in the particular case where a =
k and b = 0, it has been demonstrated that
t ≈ 2log k (10.66)
2
Example 10.3 Express 17P under the form of Eq. (10.65). Initially α =
17 + 0τ, that is, a = 17 and b = 0. Then

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