0

我正在研究二进制矩阵（1或0）的最小多项式。我知道一些算法来找到矩阵的最小多项式，例如 Berlekamp Massey。您能否向我建议一些 matlab 代码来在 Galios Field 2 中实现 Berlekamp Massey。我尝试使用 linbox lib，但需要很长时间才能完成并且没有申请二进制矩阵。这是我的矩阵

 A=[1     0     0    0; 
    0     1     0    1;
    1     1     1    1;
    1     1     1    0];

这是我的matlab代码（但我认为它不适合我在GF（2）中的问题）

function f=minPoly_Berlemap(A,b)
A=[1     0     0    0; 
    0     1     0    1;
    1     1     1    1;
    1     1     1    0];
b=[1;1;0;0];
[m n]=size(A);
A_u=[];
I=eye(n);
%% Step1
for i=1:(2*n)
    A_u(:,i)= mod(A^(i-1)*b,2);   
end
%% Step2
k=0;
g=[1];
gk=[1];
d=0;
%% Step3
while (d<n&k<n)
    %% Step4
    u_k=I(:,k+1);
    s=mod(u_k'*A_u,2);
    %% Step 5
    d = length(g)-1;
    mul_gs =mod( conv(g(end:-1:1),s),2); %multiply two polynomial
    s_g = mul_gs(d+1:end-d);  
    %% Step 6
    f=Berlekamp_Massey2(s_g);
    %% Step 7
    gk=mod(conv(f,g),2);    
    if d<n
        k=k+1;
        g=gk;
    else 
        break;
    end
end
    f=g
end
4

1 回答 1

1

您的代码存在问题：

第 1 步：而不是(A^i)*b你应该计算A*(A*(...(A*b)..))，因为这具有较低的复杂性。代替：

%% Step1 - old
for i=1:(2*n)
    A_u(:,i)= mod(A^(i-1)*b,2);   
end

有了这个：

%% Step1 - new
A_u(:,1) = b;
for i = 2:2*n
    A_u(:,i) = mod(A*A_u(:,i-1), 2);   
end

原始方法

不要过多地阅读这个问题我会建议你简单的出路：

只要看看：M, M^2, M^3, ...我们看到，那

M^3 == eye(4)  [mod 2].

这样你就知道你的多项式的次数不大于三。（因为你可以M^4用M和M^5用M^2等等替换）。

所以你的最小多项式必须是其中之一：

a_0*eye(4) + a_1*M + a_2*M^2 + a_3*M^3,a_i在{0,1}.

您可以简单地尝试所有2^4-1 = 15可能性（我们不包括所有 a_i 都为零的可能性），您会看到，这M^3 - eye(4)是您的最小多项式。

于 2014-12-29T18:51:14.033 回答