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

rt = gfroots(f,m,p) finds roots of the polynomial represented by f. 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(pm).

Note

This function performs computations in GF(pm), where p is prime. To work in GF(2m), use the roots function with Galois arrays. For details, see Roots of Polynomials. gfroots lists each root exactly once, ignoring multiplicities of roots.

rt = gfroots(f,prim_poly,p) finds roots in GF(pm) finds roots of a polynomial f using the degree-m primitive polynomial, prim_poly.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(pm) 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

Find and Display Roots of a Primitive Polynomial

This example shows how to find the roots of the primitive polynomial $2+x^3+x^4$ for GF(81) and displays each root in traditional polynomial form using the primitive element $\alpha$.

p =3;
m = 4;

Primitive polynomial for GF(81).

prim_poly = [2 0 0 1 1]; 

Find roots of the primitive polynomial.

f = prim_poly; 
[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

 
                                          
                                     alpha
 
                                         3
                                    alpha 
 
                                           2        3
                          2 alpha + 2 alpha  + alpha 
 
                                       2        3
                              2 + alpha  + alpha 

Input Arguments

f — Polynomial coefficients

polynomial character vector | row vector in ascending values

Polynomial coefficients, specified as a polynomial character vector or a row vector in ascending values.

Data Types: double | char

m — Degree of field extension

positive integer

Degree of field extension, specified as a positive integer.

Data Types: single | double

p — Prime number

2 (default) | positive integer

Prime number, specified as a positive integer.

Data Types: single | double

prim_poly — Primitive polynomial for GF(pm)

row vector

Primitive polynomial for GF(pm), specified as a row vector.

Data Types: single | double

Output Arguments

rt — Roots in exponential format

column vector

Roots in exponential format, returned as a column vector.

Data Types: double

rt_tuple — Roots in polynomial format

matrix

Roots in polynomial format, returned as a matrix.

Data Types: double

field — Field elements

matrix

Field elements, returned as a matrix.

Data Types: single | double

Version History

Introduced before R2006a