Page 141 - Hardware Implementation of Finite-Field Arithmetic

124 Cha pte r F i v e

+
and b(x) = b x m − 1 . . . + b x + b of degrees less than m over Z , the
m − 1 1 0 p
computation of c(x) = a(x)b(x) mod f(x) can be done as follows:

a(x)b(x) = ( . . . ((0x + a(x)b )x + a(x)b )x + . . . )x + a(x)b (5.8)
m − 1 m − 2 0
In order to compute Eq. (5.8), a quantity of the form s(x)x has to
be reduced modulo f(x). This can be computed as follows:
+
m
m
2
s(x)x = s x + s x m − 1 . . . + s x + s x ≡ s x + s x m − 1
m − 1 m − 2 1 0 m − 1 m − 2
2
+ . . . + s x + s x − s f(x)
1 0 m − 1
= (s − s f )x m − 1 + (s − s f )x m − 2
m − 2 m − 1 m − 1 m − 3 m − 1 m − 2
+ . . . + (s − s f )x + (0 − s f ) (5.9)
0 m − 1 1 m − 1 0
where all operations are done modulo p. If d(x) = s(x)x = d x m − 1 + . . . +
m − 1
d x + d , then using Eq. (5.9) we have that
1 0
d =− s f
0 m − 1 0
d = s − s f , i = 1, 2, . . . , m − 1 (5.10)
i i − 1 m − 1 i
Assume that the function
function multiply_by_x_zp(s,f: polynomial_m1) return
polynomial_m1
implementing Eq. (5.9) according to Eq. (5.10) and therefore returning
the polynomial s(x)x mod f(x) has been defined, where polynomial_m1
is a vector from 0 to m – 1 with coefficients in Z . Also assume that
p
the functions product(a, b) and addition_mod_f_poly(a, b) compute the
multiplication of the polynomial a(x) by b in Z (ba mod p, ba mod
p 0 1
p, . . . , ba mod p) and the addition of two polynomials a(x) and
m − 1
b(x) in Z according to Algorithm 5.2, respectively. Then the follow-
p
ing algorithm implements the MSE-first multiplication scheme given
in Eq. (5.8):
Algorithm 5.6—MSE-first multiplier

for i in 0 .. m -1 loop
c := addition_mod_f_poly(multiply_by_x_zp(C,F),
product(A,B(m-1-i)));
end loop;

An executable Ada file MSEfirst.adb, including Algorithm 5.6, is
available at www.arithmetic-circuits.org.
The circuit of Fig. 5.1 can execute the main step of Algorithm 5.6.
In order to reduce the number of computation resources, the
circuit of Fig. 5.2 can also be used: With control = 1 the circuit
computes c(x)x mod f(x), and with control = 0 it computes c(x) +
a(x)b . The minimum clock period is approximately equal to
m − 1 − i