Page 202 - Hardware Implementation of Finite-Field Arithmetic

182 Cha pte r Se v e n

for k in 0 to i loop
di(i) := (di(i) xor (a(k) and b(i-k)));
end loop;
end loop;
D <= di;
end process genD;
genE: process(a,b)
variable ei: std_logic_vector(M-2 downto 0);
begin
for i in 0 to M-2 loop
ei(i) := ‘0’;
for k in i to M-2 loop
ei(i) := (ei(i) xor (a(M-1-(k-i)) and b(k+1)));
end loop;
end loop;
E <= ei;
end process genE;
--Mastrovito multiplication, second version
mastrovitoV2: process(e,d)
variable ci, re: std_logic_vector(M-1 downto 0);
begin
for i in 0 to M-1 loop
re(i) := (R(i)(0) and E(0));
for j in 1 to M-2 loop
re(i) := (re(i) xor (R(i)(j) and E(j)));
end loop;
ci(i) := (D(i) xor re(i));
end loop;
C <= ci;
end process mastrovitoV2;
Some important irreducible polynomials will be studied in Sec.
7.6 using the above Mastrovito schemes.
7.1.5 Montgomery Multiplication
Montgome ry multiplication was first proposed for integer modular
multiplication (Montgomery modular multiplication was studied in
Chap. 3) that can avoid trial division [Mon85]. Later, it was extended
m
to finite field multiplication in GF(2 ) [KA98], where it was shown
that the operation can be simplified if a certain type of element r(x) is
m
selected. In the following, Montgomery multiplication in GF(2 ) as
proposed in [KA98] is considered.
Let f(x) be an irreducible polynomial over GF(2) that defines the
m
finite field GF(2 ). Rather than computing Eq. (7.2), the Montgomery
multiplication calculates
− 1
c(x) = a(x)b(x)r (x) mod f(x) (7.31)
where r(x) is a fixed element and gcd(r(x), f(x)) = 1. Because of Bezout’s
− 1
identity, one can find two polynomials r (x) and f’(x) such that
r(x)r (x) + f(x)f’(x) = 1 (7.32)
− 1