b_m.m

B-M 算法的matlab实现 密码学中又一重要的算法实现

function FL=B_M(a)
N=length(a);
d=zeros(1,N);f=zeros(N,N);l=zeros(1,N);

for i=1:N
    if a(i)~=0
        n0=i; 
        break;
    end
end

d(n0)=a(n0);l(n0)=n0;

for j=1:N
    f(1,j)=1;
end
f(n0+1,n0)=-a(n0);


for j=(n0+1):N
    
    for i=1:l(j-1)+1
        d(j)=d(j)+a(j+1-i)*f(i,j-1);
    end
    d(j)=mod(d(j),2);
    if d(j)==0
        for i=1:N
            f(i,j)=f(i,j-1);
        end
        l(j)=l(j-1);
    else
        for k=1:j-1
            if l(k)==l(j-1)
                m=k-1;
                break;
            end 
        end
        
        for i=1:(j-1-m)
            f(i,j)=f(i,j-1);
        end
        for i=(j-m):N
            f(i,j)=f(i,j-1)+d(j)*invmod(d(m+1),2)*f(i-(j-1-m),m);
        end
        l(j)=max(l(j-1),j-l(j-1));
    end
end


for i=1:N
    for j=1:N
        FL(i,j)=f(i,j);
    end
end
for j=1:N
    FL(N+1,j)=l(j);
end