Communications Toolbox

gfroots

Find the roots of a polynomial over a prime Galois field

Syntax

• rt = gfroots(f,m,p);
  rt = gfroots(f,prim_poly,p);
  [rt,rt_tuple] = gfroots(...);
  [rt,rt_tuple,field] = gfroots(...);
  

Description

Note    This function performs computations in GF(pm) where p is odd. To work in GF(2m), use the roots function with Galois arrays. For details, see Roots of Polynomials.

For all syntaxes, f is a row vector that gives the coefficients, in order of ascending powers, of a degree-d polynomial.

Note    gfroots lists each root exactly once, ignoring multiplicities of roots.

rt = gfroots(f,m,p) finds roots in GF(p^m) of the polynomial that f represents. m is an integer greater than or equal to d. rt is a column vector each of whose entries is the exponential format of a root. The exponential format is relative to a root of the default primitive polynomial for GF(p^m).

rt = gfroots(f,prim_poly,p) finds roots in GF(p^m) of the polynomial that f represents. rt is a column vector each of whose entries is the exponential format of a root. The exponential format is relative to a root of the degree-m primitive polynomial for GF(p^m) that prim_poly represents. m is an integer greater than or equal to d.

[rt,rt_tuple] = gfroots(...) returns an additional matrix rt_tuple, whose kth row is the polynomial format of the root rt(k). The polynomial and exponential formats are both relative to the same primitive element.

[rt,rt_tuple,field] = gfroots(...) returns additional matrices rt_tuple and field. rt_tuple is described in the paragraph above. field gives the list of elements of the extension field. The list of elements, the polynomial format, and the exponential format are all relative to the same primitive element.

Note    For a description of the various formats that gfroots uses, see Representing Elements of Galois Fields.

Examples

Roots of Polynomials contains a description and example of the use of gfroots.

As another example, the code below finds the polynomial format of the roots of the primitive polynomial 2 + x³ + x⁴ for GF(81). It then displays the roots in traditional form as polynomials in alpha. (The output is omitted here.) Because prim_poly is both the primitive polynomial and the polynomial whose roots are sought, alpha itself is a root.

• p = 3; m = 4;
  prim_poly = [2 0 0 1 1]; % A primitive polynomial for GF(81)
  f = prim_poly; % Find roots of the primitive polynomial.
  [rt,rt_tuple] = gfroots(f,prim_poly,p);
  % Display roots as polynomials in alpha.
  for ii = 1:length(rt_tuple)
     gfpretty(rt_tuple(ii,:),'alpha')
  end
  

See Also
gfprimdf

gfrepcov

gfsub