Page 139 - Hardware Implementation of Finite-Field Arithmetic

122 Cha pte r F i v e

From Eq. (5.3), the coefficients of d(x) are determined by the
following expressions:

⎧ ∑ k ab ; k = 0, ... , m−1
⎪
d = ⎨ i=0 ik i −
k 2 m−2 (5.4)
⎪ ∑ = a ki −+( m−1) b i−(m−1) ; k = m, ... 2 , m−2
⎩
m
ik
where additions and multiplications are mod p operations (performed
over Z ).
p
Assume that the function dar_mod_multiplication(x, y, m, k) com-
putes xy mod m; x, y, and m being k-bit numbers according to double,
add, and reduce multiplication mod m given in Chap. 3 (Algorithm 3.7).
Then the function poly_mult_zp(a, b) performing the polynomial mul-
tiplication of a(x) an d b(x), d(x) = a(x)b(x), where ax () =∑ i=0 a x ,
m−1
i
i
bx () =∑ m−1 b x , and dx () =∑ 2 m−2 d x , with a , b , d ∈ Z , can be easily
i
i
i=0 i i=0 i i i i p
implemented using Eq. (5.4).
After the polynomial multiplication, reduction modulo polynomial
f(x) must be performed. In the modular reduction c(x) = d(x) mod f(x),
the degree 2m − 2 polynomial d(x) is reduced by the degree m polynomial
f(x), resulting in a polynomial c(x) with degree deg(c(x)) ≤ m − 1:
c(x) = d(x) mod f(x) = (d x 2m − 2 + . . . + d x + d ) mod f(x)
2m − 2 1 0
= c x m − 1 + … + c x + c (5.5)
m − 1 1 0
The reduction modulo f(x) can be viewed as a linear mapping of
the 2m − 1 coefficients of d(x) into the m coefficients of c(x). This
mapping can be represented in matrix notation as follows:

⎛ d 0 ⎞
⎛ c ⎞ ⎛ 10 0 r 00 , r 0, m 2 ⎞ ⎜ ⎟
−
⎜ c 0 ⎟ ⎜ 01 0 r r ⎟ ⎜ d ⎟
⎜ 1 ⎟ = ⎜ 1,,0 , 1 m− 2 ⎟ ⎜ m −1 ⎟
⎜ ⎟ ⎜ ⎟ ⎜ d m ⎟ (5.6)
⎝ c ⎜ m 1⎠ ⎟ ⎜ ⎝ 00 1 r m− , 10 r m− , 1 m− 2⎠ ⎟ ⎠ ⎜ ⎜ ⎟ ⎟
−
⎜d ⎟ ⎠
⎝ 2 m −2 .
The matrix in Eq. (5.6) consists of an (m × n) identity matrix and an
(m × m – 1) matrix R named a reduction matrix. The R matrix i s a
m
function of the selected polynomial f(x) = x + f x m − 1 + . . . + f x + f .
m − 1 1 0
Therefore, to every f(x) a reduction matrix R is uniquely assigned.
The coefficients r ∈ Z of R can be recursively computed in function
j,i p
of f(x) as follows:
⎧ − fj ; = 0 ,… , m − 1 i ; = 0
⎪
r = ⎨ j (5.7)
ji , r + r r ;; j = 0 ,… ,m − 1 ; i = 1 ,… ,m−2
⎩ ⎪ j−1 i , −1 m−1 i , −1 j,0