伯利坎普－梅西算法（Berlekamp-Massey）

百度百科：Berlekamp-Massey算法可以找到给定二进制输出序列的最短线性反馈移位寄存器（LFSR）。 该算法还将在任意场中找到线性递归序列的最小多项式。

算法原理

（跟网上流传的原理方法有些不同）

算法流程

我的思路

我认为这种算法的主要难度在于给定或已算出的f i (x)对a(i+1)的计算，参考思路如下：

当然这也是最直接暴力的思路，仅供参考

程序代码

数组长度均为可调

输入

不超过数组长度的二进制序列，如0111010101（乱打的

输出

最短LFSR的特征多项式 f(x)，次数由高到低排列

#include<stdio.h>
int cb(int f,int a[],int n)//f以二进制表示系数 
{
	if(f==1) return 0;
	int c[30],i,k,b=0;
	i=0;
	while(f!=0)//f对应的系数序列c[] 
	{
		c[i]=f%2;
		f=f/2;
		i++;
		c[i]=-1;
	}
	k=i-2;//c1.place
	while(k>=0)//计算a~ 
	{
		b=b+c[k]*a[n-1];
		n--;
		k--;
	}
	return b%2;
}
int cpl(int l[],int n)//compare l[]
{
	int i;
	for(i=n;i>=0;i--)
	{
		if(i==0) return n;//all equal
		if(l[i]>l[i-1]) return i-1;//return m
	}
}
int pow(int m,int n)
{
	int s=1;
	while(n!=0)
	{
		if(n&1) s*=m;
		m*=m;
		n>>=1;
	}
	return s;
}
int cfn(int fm,int fn)//计算f[n+1] 
{
	int cm[30],cn[30],i,s;
	for(i=0;i<30;i++)
	{
		cm[i]=0;
		cn[i]=0;
	}
	i=0;
	while(fm!=0)
	{
		cm[i]=fm%2;
		fm=fm/2;
		i++;
	}
	i=0;
	while(fn!=0)
	{
		cn[i]=fn%2;
		fn=fn/2;
		i++;
	}
	for(i=0;i<30;i++) cn[i]=(cm[i]+cn[i])%2;//序列对应系数相加后模2 
	s=0;
	for(i=0;i<30;i++) if(cn[i]==1) s+=pow(2,i);
	return s;
}
int max(int a,int b)
{
	if(a>b) return a;
	return b;
}
int main()
{
	char a_str[30];
	int a[30],f[30],l[30],b[30],i=0,len,n,m,d;//max length = 30
	f[0]=1;l[0]=0;
	printf("二进制序列：");
	scanf("%s",a_str);
	while(a_str[i]!='\0') 
	{
		a[i]=a_str[i]-'0';
		i++;
	}
	len=i;
	for(n=0;n<len;n++)
	{
		if(a[n]==cb(f[n],a,n))//f[n]能生成a的前n+1位 
		{
			f[n+1]=f[n];
			l[n+1]=l[n];
		}
		else//不能生成 
		{
			if(cpl(l,n)==n)//l0=l1=...=ln 
			{
				f[n+1]=pow(2,n+1)+1;
				l[n+1]=n+1;
			}
			else
			{
				m=cpl(l,n);//lm<lm+1=...=ln
				d=(m-l[m])-(n-l[n]);
				if(d>=0) f[n+1]=cfn(f[n],(f[m]<<d));//m-lm ≥n-ln 
				else
				{
					d=-1*d;//n-ln>m-lm
					f[n+1]=cfn((f[n]<<d),f[m]);
				}
				l[n+1]=max(l[n],n+1-l[n]);
			}
		}
	}
	int s=f[n],c[30],k,q;
	i=0;
	while(s!=0)
	{
		c[i]=s%2;
		s=s/2;
		i++;
		c[i]=-1;
	}
	k=i-1;
	for(i=0;i<=k;i++) if(c[i]==1) break;
	q=i;
	printf("最短LFSR的特征多项式 f = ");
	for(i=k;i>=q;i--)
	{
		if(c[i]==1&&i!=q)
		{
			if(i!=1) printf("x^%d + ",i);
			else printf("x + ");
		}
		else if(i==q)
		{
			if(q!=0)
			{
				if(i!=1) printf("x^%d",i);
				else printf("x");
			}
			else printf("1");
		}
	}
	return 0;
}

原理和流程都是比较简单的，就是C语言写的有点多（或者大概率是我菜
用python的话就不用考虑数组长度和整型数大小（C也有一个Miracl库可以实现大数
python实现请移步隔（不记得哪的）壁

函数说明
cb()：计算a’，即通过已知的多项式f(x)求出相应的a以用于与输入的二进制序列比较
cpl()：比较l[ ]中的每一个数值，在不能生成前n+1位时使用，返回值为次小值的最大下标，若无次小值，返回当前可生成的位数n
pow()：快速指数运算
cfn()：在不能生成前n+1位时用于计算f[n+1]