This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.


Divide polynomials over Galois field


[quot,remd] = gfdeconv(b,a)
[quot,remd] = gfdeconv(b,a,p)
[quot,remd] = gfdeconv(b,a,field)



This function performs computations in GF(pm), where p is prime. To work in GF(2m), use the deconv function with Galois arrays. For details, see Multiplication and Division of Polynomials.

The gfdeconv function divides polynomials over a Galois field. (To divide elements of a Galois field, use gfdiv instead.) Algebraically, dividing polynomials over a Galois field is equivalent to deconvolving vectors containing the polynomials' coefficients, where the deconvolution operation uses arithmetic over the same Galois field.

[quot,remd] = gfdeconv(b,a) computes the quotient quot and remainder remd of the division of b by a in GF(2). a and b can be either polynomial character vectors or numeric vectors.

[quot,remd] = gfdeconv(b,a,p) divides the polynomial b by the polynomial a over GF(p) and returns the quotient in quot and the remainder in remd. p is a prime number. b, a, quot, and remd are row vectors that give the coefficients of the corresponding polynomials in order of ascending powers. Each coefficient is between 0 and p-1.

[quot,remd] = gfdeconv(b,a,field) divides the polynomial b by the polynomial a over GF(pm) and returns the quotient in quot and the remainder in remd. Here p is a prime number and m is a positive integer. b, a, quot, and remd are row vectors that list the exponential formats of the coefficients of the corresponding polynomials, in order of ascending powers. The exponential format is relative to some primitive element of GF(pm). field is the matrix listing all elements of GF(pm), arranged relative to the same primitive element. See Representing Elements of Galois Fields for an explanation of these formats.


The code below shows that

(x+x3+x4)÷(1+x)=1+x3 Remainder 2

in GF(3). It also checks the results of the division.

p = 3;
b = [0 1 0 1 1]; a = [1 1];
[quot, remd] = gfdeconv(b,a,p)
% Check the result.
bnew = gfadd(gfconv(quot,a,p),remd,p);
if isequal(bnew,b)

The output is below.

quot =

     1     0     0     1

remd =



Working over GF(3), the code below outputs those polynomials of the form xk - 1 (k = 2, 3, 4,..., 8) that 1 + x2 divides evenly.

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

The output is below.

    2 + X 
    2 + X 

In light of the discussion in Algorithms on the gfprimck reference page, along with the irreducibility of 1 + x2 over GF(3), this output indicates that 1 + x2 is not primitive for GF(9).


The algorithm of gfdeconv is similar to that of the MATLAB function deconv.

See Also

| | | |

Introduced before R2006a

Was this topic helpful?