Page 151 - Hardware Implementation of Finite-Field Arithmetic

134 Cha pte r F i v e

Algorithm 5.9—OEF multiplication
d := poly_mult_zp(a,b);
e(m-1) := d(m-1);
for i in 0 .. m-2 loop
e(i) := mod_m_addition(d(i),dar_mod_multiplication(d(m+i),
c,p,m),p,m);
end loop;
where the intermediate product d(x) of degree less than or equal to
2m − 2 is computed using the function poly_mult_zp, and where the
functions mod_m_addition and dar_mod_multiplication compute the
addition and multiplication mod p, respectively. Furthermore, in
Algorithm 5.9, c in GF(p) is the term corresponding to the
m
irreducible binomial f(x) = x – c. An executable Ada file OEF_
mult_mod_f.adb, including Algorithm 5.9, is available at www.
arithmetic-circuits.org.
m
For an OEF with f(x) = x – c, it must also be noted that the quantity
s(x)x mod f(x) given in Eq. (5.9), can be computed as follows:
s(x)x = s x + s x m − 1 + . . . + s x + s x
2
m
m − 1 m − 2 1 0
+
2
m
≡ s x + s x m − 1 . . . + s x + s x − s f(x) (5.16)
m − 1 m − 2 1 0 m − 1
+
= s x m − 1 + s x m − 2 . . . + s x + s c
m − 2 m − 3 0 m − 1
where coefficient arithmetic is done modulo p. If d(x) = s(x)x = d x m − 1
m − 1
+ . . . + d x + d , then using Eq. (5.16) we have
1 0
d = s c
0 m − 1
d = s , i = 1, 2, . . . , m − 1 (5.17)
i i − 1
Therefore, s(x)x mod f(x) requires only one multiplication mod p
when an OEF is used.
Assume that the function
function mult_x_OEF(s: polynomial_m1; c: integer) return
polynomial_m1
implementing Eq. (5.17) according to Eq. (5.16) and therefore returning
the polynomial s(x)x mod f(x) has been defined. Then the following
algorithm implements the MSE-first multiplication scheme given in
m
Algorithm 5.6 for an OEF with f(x) = x – c:
Algorithm 5.10—MSE-first multiplier for OEF

for i in 0 .. m-1 loop
d := addition_mod_f_poly(mult_x_OEF(d,c),
product(a,b(m-1-i)));
end loop;