## 8.4 OPERATIONS IN *GF*(*p*^{n})

If *f* is an irreducible polynomial then *Z*_{p}[*x*]/*f*(*x*) is the Galois field *GF*(*p*^{n}), so that every nonzero polynomial *a*(*x*) has a multiplicative inverse *a*^{−1}(*x*). Given two polynomials

a variant of the extended Euclidean algorithm (Chapter 2, Section 2.1.2) allows the expression of the greatest common divider of *f* and *a* in the form

In particular, if *gcd*(*f*, *a*) = 1 then *a*^{−1}(*x*) = *b*(*x*) mod *f*.

The following formal algorithm, in which degree(a) returns the degree of *a* and swap(a, b) interchanges *a* and *b*, computes *z*(*x*) = *a*^{−1}(*x*).

**Algorithm 8.23**

u:=f; v:=a; c:=0; e:=1;
m:=degree(u); t:=degree(v);
**if** t=0 **then** result:=(v(0))^{−1};
**else**
**while** t>0 **loop
if** m<t **then** swap(u,v); swap(c,e); swap(m,t);
q:=u(m)*(v(t))^{-1}*x^{m−t}; r:=u-(v*q); cc:=c-(e*q);
u:=v; v:=r; c:=e; e:=cc;
m:=t; t:=deg(v);
**end loop;**
z:=e*(v(0))^{-1};
**end if;**

**Example 8.7**

As *p* = 2, Algorithm 8.23 can be simplified; in particular, *u*(*m*) = *υ*^{−1}(*t*) = *υ*(0) = 1.

Compute *a*^{−1}(*x*):

Effectively,

In order to execute Algorithm 8.23, the ...