Primitive Trinomials

by Michael Monagan

Abstract: Computing primitive trinomials overfinite fields for error correcting codes and random number generators.

Application Areas/Subjects: Algebra

Keywords: finite fields, primitive polynomials, primitive elements, trinomials, overfinite fields, error correcting , random number generators

> restart:

Primitive Trinomials

This is an example of computing with in finite fields in Maple showing how to find primitive trinomials over GF(2), the finite field with two elements. These are polynomials of the form

which are `primitive' over GF(2). Primitive polynomials find utility in the generation of error correcting codes, random number generators, and the reason trinomials are of special interest is because they result in faster computation, because most of the terms are zero.

Recall that a polynomial a(x) over GF(p) of degree k is said to be primitive if

(i) it is irreducible (it does not factor over GF(p) and

(ii) the element x in GF(p^k) = Zp[x]/<a(x)> is a primitive element.

The second condition says that the sequence x^i for i=1..p^k-1 generates all the non-zero elements of the the field GF(p^k). For example, lets show that the polynomial x^4+x+1 over GF(2) is primitive. For (i) we use the Irreduc function from the Maple library.

> Irreduc( x^4+x+1) mod 2;

The algorithm Maple uses to show that a polynomial is irreducible is known as the Cantor-Zassenhaus distinct degree algorithm. For (ii), we must show that the following sequence creates all 15 non-zero polynomials of degree less than 4

> s := 1:
for i from 1 to 15 do s := s, Rem(x^i, x^4+x+1,x) mod 2 od:
s;

This is a brute force method of showing that x^i generates generates all elements of the field, and clearly it is not possible to do this for trinomials with large n, say n = 50. Here is a Maple program which computes and prints all primitive trinomials over GF(2) with degrees between 10 and 20 using a smarter approach by looking only at x^k where k divides p^k-1 the order of the multiplicative group. Note the ifactors function returns the factorization of an integer n in the format [s,[[p1,e1],...,[pm,em]]]. The Powmod function computes Rem(a^n,b,x) mod p efficiently for large n.

> readlib(ifactors):
for k from 10 to 20 do
n := ifactors(2^k-1);
trinomials := NULL;
for i from 1 to k-1 do
candidate := x^k+x^i+1;
if not Irreduc(candidate) mod 2 then next fi;
isPrimitive := true;
for j in n[2] while isPrimitive do
if Powmod(x,(2^k-1)/j[1],candidate,x) mod 2 = 1 then
isPrimitive := false
fi;
od;
if isPrimitive then trinomials := trinomials, candidate fi;
od;
if trinomials <> NULL then print("degree ".k, trinomials) fi;
od:

For higher degree, the factorization of 2^k-1 will become the bottleneck. We can improve the speed of this particular integer factorization by considering first the factorization of the polynomial

For example, for k=50 we have

> factor(x^50-1);

Therefore the factors of the integer 2^50-1 = 1125899906842623 are the factors of the integers

> subs(x=2,[op(%)]);

These integers factor as follows

> map(ifactor,%);

> convert(%,`*`);

Using this idea we can factor a number of the form 2^n-1 faster via first factoring the polynomial x^n-1. The following Maple procedure factors the integer efficiently and the factorizations of 2^90-1 and 2^100-1.

> fastifactors := proc(n) local f;
f := factor(x^n-1);
f := subs(x=2,[op(f)]);
f := map(ifactor,f);
ifactors(convert(f,`*`));
end:

> 2^90-1 = fastifactors(90);

> 2^100-1 = fastifactors(100);

A second improvement that will save half the work comes from noting the following theorem. If x^n + x^m + 1 is primitive then it's self reciprocal polynomial x^n + x^(n-m) + 1 is also primitive. Including both ideas we have the following program to compute all primitive trinomials of degree 90 to 100.

> for k from 90 to 100 do
n := fastifactors(k);
trinomials := NULL;
for i from 1 to k/2 do
candidate := x^k+x^i+1;
if not Irreduc(candidate) mod 2 then next fi;
isPrimitive := true;
for j in n[2] while isPrimitive do
if Powmod(x,(2^k-1)/j[1],candidate,x) mod 2 = 1 then
isPrimitive := false
fi;
od;
if isPrimitive then
trinomials := trinomials, candidate;
if i<k/2 then trinomials := trinomials, x^k+x^(k-i)+1 fi
fi;
od;
if trinomials <> NULL then print("degree ".k, trinomials) fi;
od:

>

>