Page 150 - Hardware Implementation of Finite-Field Arithmetic

Operations over Z [ x ]/ f ( x ) 133
p

61
31
particularly good choices of p are 2 − 1 and 2 − 1. A Type II OEF
m
has an irreducible binomial f(x) = x − 2. This OEF allows a reduction
in the complexity of extension field modular reduction, as it will be
proven later on.
The elements of an OEF can be represented by polynomials of
degree m − 1 with coefficients from the subfield GF(p). Addition and
subtraction of two field elements are implemented in a straightforward
way by adding or subtracting, respectively, the coefficients of their
polynomial representations and performing, if necessary, a reduction
modulo p. Addition and subtraction in OEFs can be implemented
using the algorithms given in Sec. 5.1.
Extension field multiplication comprises polynomial multiplica-
tion over GF(p) and a reduction modulo the irreducible binomial f(x) .
Ordinary polynomial multiplication of two field elements a(x) and
b(x) results in an intermediate product d(x) of degree less than or
equal to 2m − 2, as given in Eqs. (5.3) and (5.4). After polynomial
multiplication, the reduction c(x) = d(x) mod f(x) must be performed.
m
The reduction modulo the binomial f(x) = x – c can be represented
using Eq. (5.6) as follows:

⎛ 1 000 00 c 00 0⎞ ⎛ d 0 ⎞
⎛ c ⎞ ⎜ 0 1 00 000 c 0 0 0 ⎟ ⎜ ⎜ ⎟
⎜
0
⎜ c ⎟ ⎜ 00 1 0 ⎟ d ⎟
⎜ 1 ⎟ = ⎜ 0000 c 0 ⎟ ⎜ m − 1 ⎟ (5.14)
⎟
⎜ ⎟ ⎜ ⎜ ⎜ d m ⎟ ⎟
⎝ c ⎜ m 1⎠ ⎟ ⎜ 0000 1 0000 c⎟
−
⎟
⎜ ⎝ 000 0 0 1 000 0⎠ d ⎜ ⎜ ⎝ ⎟ ⎟
0
m
2 − 2⎠
m
The reduction matrix in Eq. (5.14) is easily computed for f(x) = x – c
using Eq. (5.7) and using the fact that d x m + i ≡ cd x mod f(x)
i
m + i m + i
[Bai98]. Therefore, from Eq. (5.14), the following general expression
for the reduced polynomial is given by:
c(x) ≡ d x m − 1 + (cd + d )x m − 2 + . . . + (cd + d ) mod f(x) (5.15)
m − 1 2m − 2 m − 2 m 0
From Eq. (5.15), it must be noted that a polynomial d(x) over GF(p) of
degree less than or equal to 2m − 2 can be reduced modulo the binomial
m
f(x) = x – c, requiring at most m − 1 multiplications by c and m − 1 additions,
where both multiplications and additions are performed in GF(p) ([Bai98],
[BP01]). It can also be noted that for a Type II OEFs with f(x) = x − 2, the
m
multiplications given in Eq. (5.15) can be implemented as shifts, therefore
reducing the complexity of the modular reduction.
The above OEF multiplication method given by Eqs. (5.14) and
(5.15) for the computation of the product e(x) = d(x) mod f(x) can be
implemented in the following algorithm: