Roots of Binary Polynomials :: Galois Field Computations (Communications Toolbox)

Communications Toolbox

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.

Roots of Polynomials

Minimal Polynomials