Page 156 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 6

Operations

m
over GF (p )

et f(x) be a polynomial of degree m > 0 over Z . If f(x) is
p
irreducible, any nonzero polynomial h(x) of the ring Z [x]/f(x)
p
−1
Lhas an inverse h (x) such that
h(x)h (x) mod f(x) = 1 (6.1)
−1
Thus Z [x]/f(x) is a finite field—an extension of the finite
p
m
field Z —also called Galois field GF(p ). Algorithms and circuits for
p
executing additions, subtractions, multiplications, and exponentia-
tions over Z [x]/f(x) have already been studied in Chap. 5. In this
p
chapter the inversion or, more generally, the division operation will
be dealt with. The problem under study is the following: given g(x)
and h(x) in Z [x]/f(x), where h(x) is a nonzero polynomial, compute
p
z(x) such that g(x) = h(x)z(x) mod f(x), that is,
z(x) = g(x)h (x) mod f(x) (6.2)
−1
As in the case of Z there are two types of algorithms for
p
computing the inverse of an element h(x) of Z [x]/f(x). A first
p
method consists of using an algorithm that allows it to express the
gcd (greatest common divisor) of two polynomials a(x) and b(x) over
Z under the form α(x)a(x) + β(x)b(x) where α(x) and β(x) are
p
polynomials over Z . Assume that a(x) = f(x) and b(x) = h(x) and
p
express the gcd of f(x) and h(x) under the form α(x)f(x) + β(x)h(x).
As f(x) is irreducible and the degree of h(x) is smaller than the
degree m of f(x), their gcd is 1, so that α(x)f(x) + β(x)h(x) = 1 and
β(x)h(x) mod f(x) = 1, that is,
h (x) = β(x) mod f(x) (6.3)
−1
To this class of algorithms belong the extended Euclidean algorithm
and the binary algorithm.

139