Page 284 - Hardware Implementation of Finite-Field Arithmetic

264 Cha pte r Ei g h t

f = e + d , for i = 0, 1, . . . , m – 1. Then the product F must be multiplied
i i
2
2
by β in order to obtain G = Fβ as
G = ( d + e)β 2 + ( d + e)β 3 + ... + d ( + e)β m + 1 (8.45)
0 1 m − 1
Using the fact that

β β + ...
β m + 1 =+ 2 + β m (8.46)
and substituting Eq. (8.46) into Eq. (8.45), the following final expres-
sion is obtained:

G = g β + g β ... + g β m
2
0 1 m − 1
= d ( + e β) + ( d + e d + + e)β 2 + d( + + d + e)β 3
+
e
m − 1 0 m − 1 1 m − 1
(8.47)
+ ... + d( + + d + e)β m
e
e
m − 2 m − 1
= d ( + e)β + d ( + d )β + d ( + d )β + ... + (d + d )β m
3
2
m − 1 0 m − 1 1 m − 1 m − 2 m − 1
where the coordinates are computed as:
g = d m 1 + e
−
0
(8.48)
g = d + d i = 12,, ... , m 1−
−
i i − 1 m 1
Therefore, the expressions given in Eq. (8.48) are the coordinates
of G in the shifted polynomial basis. Now if the inverse of the permu-
tation given in Eq. (8.43) is applied to G, then the coordinates of the
product C in the Type-I optimal normal basis are finally obtained. It
must be noted that the implementation of the permutation and
inverse permutation operations are accomplished simply by wiring.
Thus, the Type-I optimal normal basis multiplier has exactly the same
area and delay complexities as that of the polynomial basis multiplier
for AOPs given in Section 7.6.3.

8.7 FPGA Implementations
Several circuits described in this chapter have been implemented
within a Xilinx Spartan3 (speed grade-5) programmable device. The
times (period, total time) are expressed in ns. The parameters FFs and
LUTs represent the number of flip-flops and look-up tables. Every slice
includes two flip-flops and two look-up tables. All the source files are
available at www.arithmetic-circuits.org.