gfdeconv

Divide polynomials over Galois field

Syntax

[q,r] = gfdeconv(b,a)

[q,r] = gfdeconv(b,a,p)

[q,r] = gfdeconv(b,a,field)

Description

[q,r] = gfdeconv(b,a) returns the quotient q and remainder r as row vectors that specify GF(2) polynomial coefficients in order of ascending powers. The returned vectors result from the division b by a. a, b, and q are in GF(2).

For additional information, see Tips.

[q,r] = gfdeconv(b,a,p) divides two GF(p) polynomials, where p is a prime number. b, a, and q are in the same Galois field. b, a, q, and r are polynomials with coefficients in order of ascending powers. Each coefficient is in the range [0, p–1].

[q,r] = gfdeconv(b,a,field) divides two GF(p^m) polynomials, where field is a matrix containing the m-tuple of all elements in GF(p^m). p is a prime number, and m is a positive integer. b, a, and q are in the same Galois field.

In this syntax, each coefficient is specified in exponential format, specifically [-Inf, 0, 1, 2, ...]. The elements in exponential format represent the field elements [0, 1, α, α², ...] relative to some primitive element α of GF(p^m).

Examples

Divide Polynomials in GF(3)

Divide $\mathit{x}+{\mathit{x}}^3+{\mathit{x}}^4$ by $1+\mathit{x}$ in the Galois field GF(3) three times. Represent the polynomials as row vectors, character vectors, and strings.

p = 3;

Represent the polynomials using row vectors and divide them in GF(3).

b = [0 1 0 1 1];
a = [1 1];
[q_rv,r_rv] = gfdeconv(b,a,p)

q_rv = 1×4

     1     0     0     1

r_rv = 
2

To confirm the output, compare the original Galois field polynomials to the result of adding the remainder to the product of the quotient and the divisor.

bnew = gfadd(gfconv(q_rv,a,p),r_rv,p);
isequal(b,bnew)

ans = logical
   1

Represent the polynomials using character vectors and divide them in GF(3).

b = 'x + x^3 + x^4';
a = '1 + x';
[q_cv,r_cv] = gfdeconv(b,a,p)

q_cv = 1×4

     1     0     0     1

r_cv = 
2

Represent the polynomials using strings and divide them in GF(3).

b = "x + x^3 + x^4";
a = "1 + x";
[q_s,r_s] = gfdeconv(b,a,p)

q_s = 1×4

     1     0     0     1

r_s = 
2

Use the gfpretty function to display the result without the remainder in polynomial form.

gfpretty(q_s)

 
                                         3
                                    1 + X 

Check for Irreducibility and Primitiveness over GF(3^k)

In the Galois field GF(3), output polynomials of the form ${\mathit{x}}^{\mathit{k}}-1$ for $\mathit{k}$ in the range [2, 8] that are evenly divisible by $1+{\mathit{x}}^2$. An irreducible polynomial over GF(p) of degree at least 2 is primitive if and only if it does not divide ${-1+\mathit{x}}^{\mathit{k}}$ evenly for any positive integer $\mathit{k}$ less than ${\mathit{p}}^{\mathit{m}}-1$. For more information, see the gfprimck function.

The irreducibility of $1+{\mathit{x}}^2$ over GF(3), along with the polynomials that are output, indicates that $1+{\mathit{x}}^2$ is not primitive for GF($3^2$).

p = 3; m = 2;
a = [1 0 1]; % 1+x^2
for ii = 2:p^m-1
   b = gfrepcov(ii); % x^ii
   b(1) = p-1; % -1+x^ii
   [quot,remd] = gfdeconv(b,a,p);
   % Display -1+x^ii if a divides it evenly.
   if remd==0
      multiple{ii}=b;
      gfpretty(b)
   end
end

 
                                         4
                                    2 + X 
 
                                         8
                                    2 + X 

Input Arguments

b — Galois field polynomial

row vector | character vector | string

Galois field polynomial, specified as a row vector, character vector, or string. b can be either a Representation of Polynomials in Communications Toolbox or numeric vector.

a and b must both be GF(p) polynomials or GF(p^m) polynomials, where p is prime. The value of p is as specified when included, 2 when omitted, or implied when field is specified.

Example: '1 + x' is a polynomial in GF(2⁴) expressed as a character vector.

Data Types: double | char | string

a — Galois field polynomial

row vector | character vector | string

Galois field polynomial, specified as a row vector, character vector, or string. a can be either a Representation of Polynomials in Communications Toolbox or numeric vector.

a and b must both be GF(p) polynomials or GF(p^m) polynomials, where p is prime. The value of p is as specified when included, 2 when omitted, or implied when field is specified.

Example: [1 2 3 4] is the polynomial 1+2x+3x²+4x³ in GF(5) expressed as a row vector.

Data Types: double | char | string

p — Prime number

2 (default) | scalar prime number

Prime number, specified as a scalar prime number.

Data Types: double

field — m-tuple of all elements in GF(p^m)

matrix

m-tuple of all elements in GF(p^m), specified as a matrix. field is the matrix listing all elements of GF(p^m), arranged relative to the same primitive element. To generate the m-tuple of all elements in GF(p^m), use

field =gftuple([-1:p^m-2]',m,p)

where m is a positive integer. The coefficients, specified in exponential format, represent the field elements in GF(p^m). For an explanation of these formats, see Representing Elements of Galois Fields.

Data Types: double

Output Arguments

q — Galois field polynomial

row vector

Galois field polynomial, returned as a row vector of the polynomial coefficients in order of ascending powers. q is the quotient from the division of b by a and is in the same Galois field as the input polynomials.

r — Division remainder

scalar | row vector

Division remainder, returned as a scalar or a row vector of the polynomial coefficients in order of ascending powers. r is the remainder resulting from the division of b by a.

Tips

• The gfdeconv function performs computations in GF(p^m), where p is prime, and m is a positive integer. It divides polynomials over a Galois field. To work in GF(2^m), use the deconv function of the gf object with Galois arrays. For details, see Multiplication and Division of Polynomials.

• To divide elements of a Galois field, you can also use gfdiv instead of gfdeconv. Algebraically, dividing polynomials over a Galois field is equivalent to deconvolving vectors containing the coefficients of the polynomials. This deconvolution operation uses arithmetic over the same Galois field.

Version History

Introduced before R2006a