gfprimck.m

本书是电子通信类的本科、研究生辅助教材

function ck = gfprimck(a, p)
%GFPRIMCK GF(P) polynomial irreducible and primitive check.
%       CK = BFPRIMCK(A) checks the irreducible and primitive property
%       of a given GF(2) polynomial A. The meaning of the output CK is as
%       follows.
%           CK = -1   A is not a irreducible polynomial;
%           CK =  0   A is irreducible but not a primitive polynomial;
%           CK =  1   A is a primitive polynomial.
%
%       CK = BFPRIMCK(A, P) checks the irreducible and primitive property
%       of a given GF(P) polynomial A.
%
%       The polynomial represented in A is in ascending order, i.e.,
%       A = [a_0, a_1, a_2,..., a_(n-1), a_n] represents
%       A(X) = a_0 + a_1 X + a_2 X^2 +...+ a_(n-1) X^(n-1) + a_n X^n
%       a_i must be an element in GF(P).
%
%       See also GFADD, GFMUL, GFDIV, GFTUPLE

%       Wes Wang 6/8/94, 10/7/95
%       Copyright (c) 1995-96 by The MathWorks, Inc.
%       $Revision: 1.1 $  $Date: 1996/04/01 17:59:20 $

if nargin < 1
  error('Not enough input for GFPRIMCK')
elseif nargin < 2
 p = 2;
end

if ~isempty([find(a~=floor(a)), find(a<0), find(a>=p)])
        error('The polynomial coeficients must be in GF(P)')
end;

%variable assignement
a = gftrunc(a);
m = length(a) - 1;      %degree of the polynomial A
n = p^m - 1;            %degree of the checking polynomial

if (m==0) 
% case of constant only
    if (a==0)
        ck = -1;
    else
        ck = 1;
    end;
elseif (m==1)
% case of only one term
    ck = 1;
else
% general case
    % quatien and remainder computation
    [q, r] = gfdeconv([1, zeros(1, n-1), p-1], a, p);
    if max(r) ~= 0
        % Any irreducible polynomial over GF(2) of degree m divides X^(p^m-1)+1
        ck = -1;
    else
        % it is irreducible, check the primitive, go through a long division.
        % make a being a monic polynomial.
        len_a = length(a);
        if a(len_a) ~= 1
            a = rem(a * a(len_a)^(p-2), p);
        end;
        ck = 1;
        %The starting degree is one degree higher than a itself.
        i = length(a)-1;
        % if it can be divided by any x^n + 1, degree(a) < n < p^m-1 ?
        r = [zeros(1, i), 1];                            %*****
        r = gftrunc(rem(r + a * (p - r(length(r))), p));       %*****
        length_a = length(a);
        while (ck == 1) & (i < n-1)
            length_r = length(r) + 1;
            if length_r == length_a
                if max(rem([p-1, r] + a * (p - r(length_r - 1)), p)) == 0  %*****
                    % can be divided by a lower x^n + 1, not primitive
                    ck = 0;
                else
                    r = gftrunc(rem([0, r] + a * (p - r(length_r - 1)), p)); %*****
                    i = i + 1;
                end;
            elseif length_r < length_a
                len = length_a - length_r;
                r = [zeros(1, len), r];             % *****
                i = i + len;
            else
                error('computation error')
            end
        end;
    end;
end;

%--end of gfprimck--