Communications Toolbox

Polynomials over Galois Fields

You can use Galois vectors to represent polynomials in an indeterminate quantity x, with coefficients in a Galois field. Form the representation by listing the coefficients of the polynomial in a vector in order of descending powers of x. For example, the vector

• gf([2 1 0 3],4)
  

represents the polynomial Ax³ + 1x² + 0x + (A+1), where

• A is a primitive element in the field GF(2⁴).
• x is the indeterminate quantity in the polynomial.

You can then use such a Galois vector to perform arithmetic with, evaluate, and find roots of polynomials. You can also find minimal polynomials of elements of a Galois field.

Addition and Subtraction of Polynomials

To add and subtract polynomials, use the ordinary + and - operators on equal-length Galois vectors that represent the polynomials. If one polynomial has lower degree than the other, then you must pad the shorter vector with zeros at the beginning so that the two vectors have the same length. The example below shows how to add a degree-one polynomial in x to a degree-two polynomial in x.

• lin = gf([4 2],3); % A^2 x + A, which is linear in x
  linpadded = gf([0 4 2],3); % The same polynomial, zero-padded
  quadr = gf([1 4 2],3); % x^2 + A^2 x + A, which is quadratic in x
  % Can't do lin + quadr because they have different vector lengths.
  sumpoly = [0, lin] + quadr; % Sum of the two polynomials
  sumpoly2 = linpadded + quadr; % The same sum
  

Multiplication and Division of Polynomials

To multiply and divide polynomials, use the conv and deconv functions on Galois vectors that represent the polynomials. Multiplication and division of polynomials is equivalent to convolution and deconvolution of vectors. The deconv function returns the quotient of the two polynomials as well as the remainder polynomial. Examples are below.

• m = 4;
  apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
  bpoly = gf([1 1],m); % x + 1
  xpoly = gf([1 0],m); % x
  % Product is A^2 x^3 + x^2 + (A^2 + A) x + (A + 1).
  cpoly = conv(apoly,bpoly); 
  [a2,remd] = deconv(cpoly,bpoly); % a2==apoly. remd is zero.
  [otherpol,remd2] = deconv(cpoly,xpoly); % remd is nonzero.
  

Note that the multiplication and division operators described in Arithmetic in Galois Fields multiply elements or matrices, but not polynomials.

Evaluating Polynomials

To evaluate a polynomial at an element of a Galois field, use the polyval function. It behaves like the ordinary MATLAB polyval function when given exactly two input arguments. The example below illustrates how to evaluate a polynomial at several elements in a field. It also checks the results using the operators .^ and .* in the field.

• m = 4;
  apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
  x0 = gf([0 1 2],m); % Points at which to evaluate the polynomial
  y = polyval(apoly,x0)
  
  y = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
   
  Array elements = 
   
       3     2    10
  
  a = gf(2,m); % Primitive element of the field, corresponding to A.
  y2 = a.^2.*x0.^2 + (a.^2+1).*x0 + (a+1) % Check the result.
   
  y2 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
   
  Array elements = 
   
       3     2    10
  

The first element of y evaluates the polynomial at 0 and, therefore, returns the polynomial's constant term of 3.

Roots of Polynomials

To find the roots of a polynomial in a Galois field, use the roots function on a Galois vector that represents the polynomial. This function finds roots that are in the same field that the Galois vector is in. The number of times an entry appears in the output vector from roots is exactly its multiplicity as a root of the polynomial.

Note    If the Galois vector is in GF(2m), then the polynomial it represents might have additional roots in some extension field GF((2m)k). However, roots does not find those additional roots or indicate their existence.

The examples below find roots of cubic polynomials in GF(8).

• m = 3;
  cubicpoly1 = gf([2 7 3 0],m); % A polynomial divisible by x
  cubicpoly2 = gf([2 7 3 1],m);
  cubicpoly3 = gf([2 7 3 2],m);
  zeroandothers = roots(cubicpoly1); % Zero is among the roots.
  multipleroots = roots(cubicpoly2); % One root has multiplicity 2.
  oneroot = roots(cubicpoly3); % Only one root is in GF(2^m).
  

Roots of Binary Polynomials

In the special case of a polynomial having binary coefficients, it is also easy to find roots that exist in an extension field. This because the elements 0 and 1 have the same unambiguous representation in all fields of characteristic two. To find roots of a binary polynomial in an extension field, apply the roots function to a Galois vector in the extension field whose array elements are the binary coefficients of the polynomial.

The example below seeks roots of a binary polynomial in various fields.

• gf2poly = gf([1 1 1],1); % x^2 + x + 1 in GF(2)
  noroots = roots(gf2poly); % No roots in the ground field, GF(2)
  gf4poly = gf([1 1 1],2); % x^2 + x + 1 in GF(4)
  roots4 = roots(gf4poly); % The roots are A and A+1, in GF(4).
  gf16poly = gf([1 1 1],4); % x^2 + x + 1 in GF(16)
  roots16 = roots(gf16poly); % Roots in GF(16)
  checkanswer4 = polyval(gf4poly,roots4); % Zero vector
  checkanswer16 = polyval(gf16poly,roots16); % Zero vector
  

The roots of the polynomial do not exist in GF(2), so noroots is an empty array. However, the roots of the polynomial exist in GF(4) as well as in GF(16), so roots4 and roots16 are nonempty.

Notice that roots4 and roots16 are not equal to each other. They differ in these ways:

• roots4 is a GF(4) array, while roots16 is a GF(16) array. MATLAB keeps track of the underlying field of a Galois array.
• The array elements in roots4 and roots16 differ because they use representations with respect to different primitive polynomials. For example, 2 (which represents a primitive element) is an element of the vector roots4 because the default primitive polynomial for GF(4) is the same polynomial that gf4poly represents. On the other hand, 2 is not an element of roots16 because the primitive element of GF(16) is not a root of the polynomial that gf16poly represents.

Minimal Polynomials

The minimal polynomial of an element of GF(2^m) is the smallest-degree nonzero binary-coefficient polynomial having that element as a root in GF(2^m). To find the minimal polynomial of an element or a column vector of elements, use the minpol function.

The code below finds that the minimal polynomial of gf(6,4) is D² + D + 1 and then checks that gf(6,4) is indeed among the roots of that polynomial in the field GF(16).

• m = 4;
  e = gf(6,4);
  em = minpol(e) % Find minimal polynomial of e. em is in GF(2).
   
  em = GF(2) array. 
   
  Array elements = 
   
       0     0     1     1     1
  
  emr = roots(gf([0 0 1 1 1],m)) % Roots of D^2+D+1 in GF(2^m)
   
  emr = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
   
  Array elements = 
   
       6
       7
  

To find out which elements of a Galois field share the same minimal polynomial, use the cosets function.

Signal Processing Operations in Galois Fields

Manipulating Galois Variables