Page 29 - Hardware Implementation of Finite-Field Arithmetic

12 Cha pte r O n e

Definitions 1.19
1. Given two polynomials g (x) and h(x), h(x) divides g (x) (or
h(x) is a divisor of g (x)) if there exists a polynomial q (x) such
that g (x) = q (x)h(x).
2. Given two polynomials g (x) and h(x), not both equal to 0, the
greatest common divisor of g (x) and h(x) is the monic polynomial
of greatest degree which divides both g (x) and h(x).
3. gcd(0, 0) = 0.
4. A polynomial f (x) of degree at least 1 is said to be irreducible
if it cannot be written as the product of two polynomials, each
of positive degree.

A variant of the Euclidean algorithm for polynomials [GG03]
expresses the greatest common divisor of two polynomials g (x) and
h(x) in the form

gcd( g, h) = b(x)g (x) + c(x)h(x)
The algorithm is based on the fact that if u(x) and v(x) are two
polynomials such that
deg (u) = m deg (v) = t and m > t

that is,

m
u(x) = u x + u x m − 1 + . . . + u x + u
m m − 1 1 0
t − 1
t
v(x) = v x + v x + . . . + v x + v
t t − 1 1 0
then
t
− 1 m − t
− 1 m − t
t − 1
v(x)u (v ) x = (v x + v x + . . . + v x + v )u (v ) x
m t t t − 1 1 0 m t
= u x + r’(x)
m
m
where deg (r’) < m, so that
u(x) = (v(x)u (v ) x − r’(x)) + u x m − 1 + . . . + u x + u
− 1 m − t
m t m − 1 1 0
= v(x)u (v ) x + r (x) (1.4)
− 1 m − t
m t
where
r (x) = u x m − 1 + . . . + u x + u − r’(x)
m − 1 1 0
so that
deg (r) < m and max(deg (r), deg (v)) < deg (u)
Furthermore,
gcd(u, v) = gcd(v, r)