Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

8.4 OPERATIONS IN GF(pⁿ)

If f is an irreducible polynomial then Z_p[x]/f(x) is the Galois field GF(pⁿ), so that every nonzero polynomial a(x) has a multiplicative inverse a⁻¹(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⁻¹(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⁻¹(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))⁻¹; 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) = υ⁻¹(t) = υ(0) = 1.

Compute a⁻¹(x):

Effectively,

In order to execute Algorithm 8.23, the ...