Page 188 - Hardware Implementation of Finite-Field Arithmetic

m
Operations over GF (2 )—Polynomial Bases 169

entity classic_multiplication is
port (
a, b: in std_logic_vector(M-1 downto 0);
c: out std_logic_vector(M-1 downto 0)
);
end classic_multiplication;
The VHDL architecture is the following:

inst_mult: poly_multiplier port map(a => a, b => b,
d => d);
inst_reduc: poly_reducer port map(d => d, c => c);
That is the simple instantiation of the poly_multiplier and poly_reducer
components given in Fig. 7.1.

7.1.2 Karatsuba-Ofman Polynomial Multiplication
The K aratsuba-Ofman algorithm ([KO63], [RMSC06]) is a recursive
method for efficient polynomial multiplication or efficient multipli-
cation in positional number systems. It is known [Paa94] that two
arbitrary polynomials in one variable of degree less or equal to m − 1
m
with coefficients from a field GF(2 ) can be multiplied with not more
2
2
than m multiplications in GF(2 ) and (m − 1) additions in GF(2 ). The
m
m
Karatsuba-Ofman algorithm provides a recursive algorithm which
reduces the above multiplicative and additive (for large enough m)
complexities. A Karatsuba-Ofman algorithm restricted to polynomi-
als, where m = 2 with t an integer, is given in [Paa94] and is outlined
t
as follows:
m
Let a(x) and b(x) be two elements in GF(2 ). We are interested in
finding the product d(x) = a(x)b(x), with degree ≤ 2m – 2. Both elements
can be represented in the polynomial basis as
+
ax () = x m/2 x ( m/ −1 a + ... + a ) + x ( m/ −21 a + ... a ) = x m/ 2 A + A
2
m−1 m/2 m/221− 0 H L
+
−
+
−
bx() = x m/ 2 x ( m/ 2 1 b + ... b )( m/ 21 b + ... b ) = x m/ 2 B B + B
+ x
−
m −1 1 m/ 2 m/ 21 0 H L
(7.8)
Using Eq. (7.8), the polynomial product is given as
m
d x () = x A B + x m/2 ( A B + AB )+ AB (7.9)
H H H L L H L L
1
()
Let us define the following auxiliary polynomials M ():
x
M () = A x B x ()
1 ()
x
()
0 L L
1 ()
( )][
M ( x) [= A x ( )+ A x B x()+ B x()] (7.10)
1 L H L L H
M () = A x B x()
() 1
x
()
2 H H