How to implement a Berlekamp–Massey algorithm? Explained with easy example

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.

How to implement a Berlekamp–Massey algorithm? Explained with easy example # 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

Comments

vijayanandrp5:43 AM
https://cocalc.com/share/public_paths/1d32f52ed8182f7f744a166db4a92b06e932ba2a

https://slideplayer.com/slide/13475838/

https://www.sagemath.org/files/kohel-book-2008.pdf&clen=626260&chunk=true

www.sagemath.org/files/thesis/nguyen-thesis-2009.pdf&clen=972814&chunk=true

ReplyDelete
Replies
vijayanandrp5:44 AM
https://wiki.sagemath.org/interact/cryptography#RSA
ReplyDelete
Replies

Add comment

Developer Notes

Search This Blog

How to implement a Berlekamp–Massey algorithm? Explained with easy example

Comments

Post a Comment