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

^{n}

If *f* is an irreducible polynomial then *Z _{p}*[

*x*]/

*f*(

*x*) is the Galois field

*GF*(

*p*), so that every nonzero polynomial

^{n}*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**

**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 ...

Get *Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.