Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

8.2 OPERATIONS IN GF(p)

If p is a prime number, then Z_p is the Galois field GF(p), and every nonzero element y of Z_p has an inverse y⁻¹. Unless p is small—in which case all inverses could have been previously computed and stored in a table—the computation of z = x⁻¹ mod p is based on the extended Euclidean algorithm (Chapter 2, Section 2.1.2), which allows the expression of the greatest common divider of two natural numbers x and y in the form

where b and c are integers. Given x and p, the computation of z = x⁻¹ mod p is made up of a sequence of integer divisions:

It has been demonstrated (Chapter 2, Section 2.1.2) that r(i) = b(i).p + c(i).x, so that

Taking into account that

and

after some finite number of steps, a remainder r(i + 2) is obtained such that

so

and

The corresponding algorithm ...