gfroots

Find roots of polynomial over 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(p^m), where p is prime. To work in GF(2^m), use the roots function with Galois arrays. For details, see Roots of Polynomials.

For all syntaxes, f is a polynomial character vector or 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. 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.

[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 preceding paragraph. 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.

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 alph. (The output is omitted here.) Because prim_poly is both the primitive polynomial and the polynomial whose roots are sought, alph 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

Version History

Introduced before R2006a