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

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 following procedures must be defined:

• the procedure

  procedure degree (a: in polynomial; deg: out natural);

  computes the degree deg of a;

• the procedure

  procedure invert (a: in coefficient; p: in module; b: out coefficient);

  computes a⁻¹ mod p; Algorithm 8.16 could be used;

• the procedure by_coefficient has already been defined;
• the procedure

  procedure add (a, b: in polynomial; p: in module; c: out polynomial);

  computes the sum of two polynomials; Algorithm 8.17 could be used;

• the procedure

  procedure sub (a, b: in polynomial; p: in module; c: out polynomial);

  computes the difference of two polynomials; Algorithm 8.18 could be used;

• the procedure

  procedure shift (a: in polynomial; k: in natural; c: out polynomial);

  computes c(x) = a(x).x^k; it is equivalent to a k-position right-shift of the coefficients of a, with the k lower-degree coefficients set to 0.

The following algorithm is deduced from Algorithm 8.23 and from the previous procedure definitions (zero and one stand for the polynomials 0 and 1, respectively):

Algorithm 8.24 Inversion in GF(pⁿ)

A different method, based on a modification of the Itoh–Tsujii algorithm ([ITO1988]), can be used if f(x) is a binomial ([WOO2000], [BAI2001]). First observe that if r = 1 + p + p² + … + pⁿ⁻¹, then (Chapter 2, Section 2.2.4) (a(x))^r is an element of Z_p (a 0-degree polynomial). As

the problem is reduced to the computation of exponential functions in GF(pⁿ) and to the inversion in GF(p).

The following formal algorithm computes z(x) = a⁻¹(x).

Algorithm 8.25

In order to execute the preceding algorithm the following procedures must be defined:

• the procedure

  procedure multiply (a, b, f: in polynomial; p: in module;
  z: out polynomial);

  computes the product of a by b modulo f; Algorithm 8.20, 8.21, or 8.22 could be used;

• the procedures by_coefficient and invert have already been defined;
• the procedure

  procedure exponentiation (a, f: in polynomial; p: in
  module; i: in natural; b: out polynomial);

  computes a^r(i) modulo f, where r(i) = pⁱ.

It remains to generate the preceding procedure. First recall (Chapter 2, Section 2.2.5) that if α, β, …, γ are elements of GF(pⁿ), then

More generally, if r(i) = pⁱ, then

Observe also that, given a coefficient a_k (an element of Z_p), then

and, more generally,

From (8.17) and (8.18) the following relation is deduced:

Assume now that f is a binomial

and that n divides p − 1 (p mod n = 1), so that

Then

The values of

can be computed in advance (an algorithm for computing f_ki is given in Appendix 8.1), so that

The corresponding exponentiation procedure is the following:

procedure exponentiation (a, f: in polynomial; p: in module;
  i: in natural; b: out polynomial) is
begin
  b(0):=a(0);
  for k in 1..n−1 loop modular_product (f(k,i), a(k), p, b(k));
end loop;
end procedure;

The complete inversion algorithm is deduced from Algorithm 8.25.

Algorithm 8.26 Inversion, Second Version

In order to reduce the number of calls to the exponentiation procedure the following property can be used.

Property 8.1 If s = 1 + p + p² + … + p^k and t = 1 + p + p² + … + p^l, where k is odd and l = (k − 1)/2, then

where u = p^k−l.

Proof

where

so that

If k+1 is a power of 2, that is, k = 2^m − 1, then l = 2^m−1 − 1, and the same decomposition can be recursively applied. The following algorithm computes z(x) = (a(x))^s, where s = 1 + p + p² + · · · + p^k with k = 2^m − 1.

Algorithm 8.27

b(0):=a;
for j in 0..m−1 loop
   exponentiation (b(2*j), f, p, 2**j, b(2*j+1));
   multiply (b(2*j), b(2*j+1), f, p, b(2*(j+1)));
end loop;
z:=b(2*m);

Example 8.8 k = 7, m = 3; in the following computation scheme r(i) stands for pⁱ, so that r(i).r(j) = r(i + j).

Assume now that n−1 is a power of 2, that is,

Then

and

The preceding algorithm can be used for computing

It remains to compute

and

The complete inversion algorithm, when

is the following.

Algorithm 8.28 Inversion, Third Version

Observe that the main iteration is executed m times instead of n − 1 = 2^m times as in Algorithm 8.26.

Example 8.9 If p = 239 and f(x) = x¹⁷ − 2, then Algorithm 828 can be applied:

the coefficients f_ki can be computed with Algorithm A 8.1.

Another example is the binomial x⁶−2 with

As n − 1 is not a power of 2, Algorithm 8.28 must be slightly modified.