Berlekamp–Massey algorithm

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. I have used sage for computing this program.

# Berlekamp-Massey Algorithm

#from __future__ import print_function

s = [GF(2)(0), 0, 1, 0, 0, 0, 0, 0, 1, 1, 0] #input sequence

n = len(s)

C = [GF(2)(1)]
B = [GF(2)(1)]
temp = []
T = []
L = 0
N = 0
m = -1

print '----- n',n
print '-----------------------------------------------------------------------'
while N < n: 
    temp = B      
    d = s[N]        
    for i in range(1,L+1):        
        d = d + C[i]*s[N-i] 
    print '----- d ',d    
    if d == 1:
        T = C
        temp = [ 0 for i in range(int(N-m))] + temp    
        
        if len(C) < len(temp):
            C = C + [0 for i in range(len(temp)-len(C))]     
        else:
     temp = temp + [0 for i in range(len(C)-len(temp))]  
      
        for i in range(len(C)):
            C[i] = C[i] + temp[i]
            
        print '----- temp',temp
        print '----- C',C
        
        if L <= N/2:
            L = int(N + 1 - L)
            m = int(N)
            B = T                    
    N = N + 1   
    print '-----------------------------------------------------------------------' 
    print '----- N',N
    print '----- L',L
    

j = 0
print '-----------------------------------------------------------------------'
print 'Solution is ', #Output registers 
for i in C:
    if j < len(C)-1:
        if i == 1:
            print i,'x^(',j,')+',
    else:
        if i == 1:
            print i,'x^(',j,')'
    j+=1