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
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).
As p = 2, Algorithm 8.23 can be simplified; in particular, u(m) = υ−1(t) = υ(0) = 1.
In order to execute Algorithm 8.23, the ...