Page 99 - Hardware Implementation of Finite-Field Arithmetic

82 Cha pte r T h ree

Obviously, the Montgomery algorithm gives the shortest com-
putation time. As pointed out in Sec. 3.4.3.1, the Montgomery method
is effective when many multiplications involving a reduced number
of different operands are performed, that is, when the initial encod-
ing (operands → T(operands)) and the final decoding (results → T −1
(results)) do not substantially increase the computation time. This is
x
the case when computing an exponential function such as y . If a
single multiplication must be performed, the other algorithms
should be considered.

3.5 Exponentiation
x
Given x and y belonging to Z = {0, 1, . . . , m − 1} , compute z = y
m
mod m. Assume that m is a k-bit number and that x is represented in
+
base 2, that is x = x · 2 k − 1 + x · 2 k − 2 . . . + x · 2 . Then z can be
0
k − 1 k − 2 0
written in the form [Knu81]
x
x
z = (( ... (1 2 y x k−1 ) 2 y x k−2 ) ... 2 y ) 2 y 0 mod m
2
)
d
1
to which corresponds the following algorithm:
Algorithm 3.13—Base 2 mod m exponentiation, MSB-first
e := 1;
for i in 1 .. k loop
e := (e*e) mod m ;
if binary_x(k-i) = 1 then e := (e*y) mod m; end if;
end loop;
z := e;
An executable Ada file mod_m_exponentiation_msb.adb, inclu-
ding Algorithm 3.13, is available at www.arithmetic-circuits.org.
This algorithm includes between k and 2k mod m products.
Nevertheless all the operands are either 1, y, or a previously obtained
value (e) so that an alternative solution is the use of the Montgomery
product. The computation is performed as follows:

Substitute the initial operands 1 and y by T(1) = 2 mod m and T(y) =
k
MP(y, exp_2k) where exp_2k = 2 mod m
2.k
Execute the main loop of Algorithm 3.13, substituting the mod m
products by Montgomery products
− 1
Compute T (e) = MP(e, 1)
Assume that exp_k = 2 mod m and exp_2k = 2 mod m have been
2k
k
previously computed and that the function mp that computes the
Montgomery product has been defined: