Page 324 - Hardware Implementation of Finite-Field Arithmetic

304 Cha pte r T e n

R_I := 1;
if Q_Infinity then Xq := Xp; Yq := Yp;
Q_Infinity := False;
else Point_Addition(Xp, Yp, Xq, Yq, F, New_Xq,
New_ Yq);
Xq := New_Xq; Yq := New_Yq;
end if;
else
R_I := -1;
if Q_Infinity then Xq := Xp; Yq := Add(Xp, Yp);
Q_Infinity := False; -- Q := Q-P = -P
else
Point_Addition(Xp, Add(Xp, Yp), Xq, Yq, F,
New_Xq, New_Yq); Xq := New_Xq; Yq := New_Yq;
end if;
end if;
Xp := Product_Mod_F(Xp, Xp, F);
Yp := Product_Mod_F(Yp, Yp, F);
--update a and b
Old_A := A; A := B + Mu*(Old_A - R_I)/2;
B := (R_I - Old_A)/2;
end loop;
Xr := Xq; Yr := Yq;

An executable Ada file frobenius_point_multiplication.adb,
including Algorithm 10.9, is available at www.arithmetic-circuits.org.
To summarize, doubling has been substituted by squaring, a simple
operation over a binary field. Furthermore, among two successive
coefficients r, at least one is equal to 0. Thus, according to Eq. (10.66),
i
an upper bound s of the number of nonzero coefficients r is given by
i
s ≈ log k ≈ m (10.69)
2
Thus, the computation of kP includes at most m complex
operations (adding or subtracting), and the total computation
time should be roughly half the computation time of that of
the basic algorithms.

10.5 Example of Implementation
As an example of application of the finite field operations, point-
multiplication Algorithm 10.9 over a particular elliptic curve will be
implemented. Consider the Koblitz curve
2
3
2
y + xy = x + x + 1 (10.70)
163
over GF(2) and the extension field L = GF(2 ). A polynomial
representation based on the irreducible polynomial
3
7
6
f(z) = z 163 + z + z + z + 1 (10.71)
will be used.