Page 318 - Hardware Implementation of Finite-Field Arithmetic

298 Cha pte r T e n

end if;
end loop;
R := A;

Every step of Algorithm 10.4 includes one point-doubling and one
point-addition. Therefore, the complexity is similar to that of the
classical point-multiplication algorithms. Nevertheless, the fact that
at each step the value of both s P and s P + P are known allows
j j
simplifying the computation in the case of the nonsupersingular
3
2
m
2
curve y + xy = x + ax + b over GF(2 ). The following property is
used: If A = (x , y ) ≠∞ and B = (x , y ) ≠∞ are two different points of
A A B B
the curve and if A ≠ − B, then the x-coordinates x and x of
A + B A − B
A + B and A − B are related by the following relation x = x +
A + B A − B
− 1 2
x (x + x ) − 1 + (x (x + x ) ) . If furthermore A = sP and B = (s + 1)P for
B A B B A B j j
some j, then A - B = - P, x = x , and
A-B P
− 1 2
x = x + x (x + x ) − 1 + (x (x + x ) ) (10.44)
A + B P B A B B A B
If P is assumed to be different from ∞, A = s P and B = (s + 1)P is
j j
always different. If at some step x = x , then A = −B and A + B= ∞.
A B
Regarding the point-doubling, according to Eq. (10.17) with b = 1
x = x + b/x if x ≠ 0 and
2
2
A + A A A A
(0, y ) + (0, y ) = (0, y ) − (0, y ) = ∞ (10.45)
A A A A
and similar relations hold for computing B + B.
Thus, Algorithm 10.4 can be executed with the x-coordinates of
the successive A and B points. A final step will compute the missing
y-coordinate of the result. It is based on the following property: If P =
(x , y ), where x ≠ 0, kP = (x , y ) and (k + 1)P = (x , y ), then
P P P A A B B
y = x − 1 (x + x )[(x + x )(x + x ) + x + y ] + y (10.46)
2
A P A P A P B P P P P
Therefore, Montgomery Algorithm 10.4 consists of t point-additions
and t point-doubling operations, where the order of magnitude
[Eq. (10.25)] of t is m. The number of operations is the same as in basic
Algorithms 10.2 and 10.3. Nevertheless, in most point-operations the
y-coordinate is not computed, so that the algorithm complexity is
roughly halved.
The Montgomery method could also be used in projective or
mixed coordinates. For that, Eqs. (10.44), (10.45), and (10.46) must be
expressed using projective coordinates for A and B. Assume that
c = d = 1 (standard projective coordinates) so that x = X /Z and x =
A A A B
X /Z . Then, according to Eq. (10.44),
B B
x = x + X Z /(X Z + X Z ) + (X Z /(X Z + X Z )) 2
A + B P B A A B B A B A A B B A
Let
2
Z = (X Z + X Z ) (10.47)
A + B A B B A