O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8.4 OPERATIONS IN GF(pn)

If f is an irreducible polynomial then Zp[x]/f(x) is the Galois field GF(pn), so that every nonzero polynomial a(x) has a multiplicative inverse a−1(x). Given two polynomials

image

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

image

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*xm−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

image

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

Compute a−1(x):

image

Effectively,

image

In order to execute Algorithm 8.23, the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required