Primitive Polynomials and Element Representations :: Galois Field Computations (Communications Toolbox)

Communications Toolbox

Primitive Polynomials and Element Representations

This section builds on the discussion in Creating a Galois Array by describing how to specify your own primitive polynomial when you create a Galois array. The topics are

If you perform many computations using a nondefault primitive polynomial, then see Speed and Nondefault Primitive Polynomials as well.

Specifying the Primitive Polynomial

The discussion in How Integers Correspond to Galois Field Elements refers to a primitive element, which is a root of a primitive polynomial of the field. When you use the gf function to create a Galois array, the function interprets the integers in the array with respect to a specific default primitive polynomial for that field, unless you explicitly provide a different primitive polynomial. A list of the default primitive polynomials is on the reference page for the gf function.

To specify your own primitive polynomial when creating a Galois array, use a syntax like

c = gf(5,4,25) % 25 indicates the primitive polynomial for GF(16).

instead of

c1= gf(5,4); % Use default primitive polynomial for GF(16).

The extra input argument, 25 in this case, specifies the primitive polynomial for the field GF(2^m) in a way similar to the representation described in How Integers Correspond to Galois Field Elements. In this case, the integer 25 corresponds to a binary representation of 11001, which in turn corresponds to the polynomial D⁴ + D³ +1.

Note When you specify the primitive polynomial, the input argument must have a binary representation using exactly m+1 bits, not including unnecessary leading zeros. In other words, a primitive polynomial for GF(2^m) always has order m.

When you use an input argument to specify the primitive polynomial, the output reflects your choice by showing the integer value as well as the polynomial representation.

d = gf([1 2 3],4,25)

d = GF(2^4) array. Primitive polynomial = D^4+D^3+1 (25 decimal)
 
Array elements = 
 
     1     2     3

Note After you have defined a Galois array, you cannot change the primitive polynomial with respect to which MATLAB interprets the array elements.

Finding Primitive Polynomials

You can use the primpoly function to find primitive polynomials for GF(2^m) and the isprimitive function to determine whether a polynomial is primitive for GF(2^m). The code below illustrates.

m = 4;
defaultprimpoly = primpoly(m) % Default primitive poly for GF(16)
allprimpolys = primpoly(m,'all') % All primitive polys for GF(16)
i1 = isprimitive(25) % Can 25 be the prim_poly input in gf(...)?
i2 = isprimitive(21) % Can 21 be the prim_poly input in gf(...)?

The output is below.

Primitive polynomial(s) = 
 
D^4+D^1+1

defaultprimpoly =

    19

Primitive polynomial(s) = 
 
D^4+D^1+1
D^4+D^3+1

allprimpolys =

    19
    25

i1 =

     1

i2 =

     0

Effect of Nondefault Primitive Polynomials on Numerical Results

Most fields offer multiple choices for the primitive polynomial that helps define the representation of members of the field. When you use the gf function, changing the primitive polynomial changes the interpretation of the array elements and, in turn, changes the results of some subsequent operations on the Galois array. For example, exponentiation of a primitive element makes it easy to see how the primitive polynomial affects the representations of field elements.

a11 = gf(2,3); % Use default primitive polynomial of 11.
a13 = gf(2,3,13); % Use D^3+D^2+1 as the primitive polynomial.
z = a13.^3 + a13.^2 + 1 % 0 because a13 satisfies the equation
nz = a11.^3 + a11.^2 + 1 % Nonzero. a11 does not satisfy equation.

The output below shows that when the primitive polynomial has integer representation 13, the Galois array satisfies a certain equation. By contrast, when the primitive polynomial has integer representation 11, the Galois array fails to satisfy the equation.

z = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)
 
Array elements = 
 
     0


nz = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)
 
Array elements = 
 
     6

The output when you try this example might also include a warning about lookup tables. This is normal if you did not use the gftable function to optimize computations involving a nondefault primitive polynomial of 13.

Example: Representing a Primitive Element

Arithmetic in Galois Fields