Page 108 - Hardware Implementation of Finite-Field Arithmetic

CHAPTER 4

Operations

over GF(p)

I f p is prime, any nonzero element y of the ring Z has an inverse
p
such that
− 1
y
yy mod p = 1 (4.1)
− 1
Thus Z is a finite field, also called Galois field, GF(p) . Algorithms
p
and circuits for executing additions, subtractions, multiplications,
and exponentiations over Z have already been studied in Chap. 3. In
p
this chapter the inversion or, more generally, the division operation
will be dealt with. The problem under study is the following: given x
and y in Z , where y ≠ 0, compute z such that x = yz mod p, that is,
p
− 1
z = xy mod p (4.2)
Observe that if p = 2, then y − 1 = 1, and z = x. So, throughout this
chapter p will be assumed to be a k-bit natural greater than 2. In
particular k must be greater than 1.
A first method for computing the mod p inverse of an element y
of Z consists of using an algorithm that allows it to express the gcd
p
(greatest common divisor) of two naturals a and b under the form of a
linear combination αa +βb of a and b where α and β are integers.
Assume that a = p and b = y and express the gcd of p and y under the
form αp + βy. As p is prime and y smaller than p, their gcd is 1, so that
αp + βy = 1 and βy mod p = 1, that is,
y − 1 =β mod p (4.3)

To this class of algorithms belong extended Euclidean algorithm and
the binary algorithm .
Another method is based on Fermat’s little theorem that states that
y p − 1 mod p = 1 for any nonzero y. Thus, y p − 2 y mod p = 1 and

y − 1 = y p − 2 mod p (4.4)
In this way inversion is substituted by exponentiation.
91