Implementation of Berlekamp-Massey Algorithm

Introduction

The Berlekamp-Massey algorithm is an efficient algorithm for determining the linear complexity of a finite binary sequence sn of length n. The algorithm takes n iterations, with the N^th iteration computing the linear complexity of the subsequence sN consisting of the first N terms of sn. Returned value (L) is the length of the shortest linear feedback shift register sequence that generates all bits in sequence sn.
(Used in NIST statistical test suite - "Linear Complexity Test".)

The Code

    // Implementation of Berlekamp-Massey algorithm for calculating linear 
    // complexity of binary sequence
    // s = byte array with binary sequence
    // returns Length of LFSR with smallest length which generates s
    // for an example: int L=BerlekampMassey(new byte[] {1,0,1,0,1,1,1,0,1,0})
    //        reference: "Handbook of Applied Cryptography", p201

    public static int BerlekampMassey(byte[] s)                
    {
        int L, N, m, d;
        int n=s.Length;
        byte[] c=new byte[n];
        byte[] b=new byte[n];
        byte[] t=new byte[n];

        //Initialization
        b[0]=c[0]=1;
        N=L=0;
        m=-1;
                
        //Algorithm core
        while (N<n)
        {
            d=s[N];
            for (int i=1; i<=L; i++)
            d^=c[i]&s[N-i];            //(d+=c[i]*s[N-i] mod 2)
            if (d==1)
            {
                Array.Copy(c, t, n);    //T(D)<-C(D)
                for (int i=0; (i+N-m)<n; i++)
                    c[i+N-m]^=b[i];
                if (L<=(N>>1))
                {
                    L=N+1-L;
                    m=N;
                    Array.Copy(t, b, n);    //B(D)<-T(D)
                }
            }
            N++;
        }
        return L;
    }
}

Finally

Sorry, but this might only be useful to those freaks (like me:) that work on statistical tests and/or cryptanalysis. I just needed to put this on the Web because I couldn't find some useful implementation out there.

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)