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 is the following.

Algorithm 8.16 Inversion in Z_p

r_i:=p; r_iplus1:=x; c_i:=0; c_iplus1:=1;
while r_iplus1>1 loop
  q:=r_i/r_iplus1; r_iplus2:=r_i mod r_iplus1;
  c_iplus2:=(c_i-q*c_iplus1) mod p;
  r_i:=r_iplus1; r_iplus1:=r_iplus2; c_i:=c_iplus1;
  c_iplus1:=c_iplus2;
end loop;
z:=c_iplus1;

As a matter of fact, it can be demonstrated that − p/2 < c(i) < p/2 so that, in the preceding algorithm, it is not necessary to perform the mod p reduction at each step. The reduction can be performed at the end of the computation, substituting the last instruction by

if c_iplus1<0 then z:=c_iplus1+p; else z:=c_iplus1; end if;

Example 8.6 Compute the inverse of 114 mod 239: