Learn more about Communications Toolbox

Polynomials over Galois Fields

On this page…
Section Overview Addition and Subtraction of Polynomials Multiplication and Division of Polynomials Evaluating Polynomials Roots of Polynomials Roots of Binary Polynomials Minimal Polynomials

Section Overview

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.

Back to Top

Addition and Subtraction of Polynomials

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

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

Back to Top

Multiplication and Division of Polynomials

To multiply and divide polynomials, use conv and deconv 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.

The multiplication and division operators in Arithmetic in Galois Fields multiply elements or matrices, not polynomials.

Back to Top

Evaluating Polynomials

To evaluate a polynomial at an element of a Galois field, use polyval. It behaves like the ordinary MATLAB polyval function when given exactly two input arguments. The example below evaluates a polynomial at several elements in a field and checks the results using .^ 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)

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.

The output is below.

y = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
     3     2    10


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.

Back to Top

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), 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).

Back to Top

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 is 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 the 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.

Back to Top

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).

emr = roots(gf([0 0 1 1 1],m)) % Roots of D^2+D+1 in GF(2^m)

The output is

em = GF(2) array. 
 
Array elements = 
 
     0     0     1     1     1


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.

Back to Top

Signal Processing Operations in Galois Fields

Manipulating Galois Variables

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS