Playing with LFSR in sage
Hi there,
so this is only half a sage question and half a math question, I think. I'm trying to play around with LFSRs. Please help a computer scientist understand :-)
Let's say I have a 16 bit LFSR that is defined by the polynomial
poly = x^16 + x^14 + x^13 + x^11 + 1
(that's the Wikipedia polynomial from http://en.wikipedia.org/wiki/Linear_f...)
Now I have some code that gives me the whole bitsequence the polynomial generates. But I want to understand the mathematical side and would like to get the same bit sequence by doing polynomial division in sage. But I haven't really understood what the LFSR is mathematically, I think. Here's my pathetic attempt:
P.<x> = GF(2)[] poly = x^16 + x^14 + x^13 + x^11 + 1 state = x^2 for i in range(20): outbit = state // poly state = state % poly print(outbit, state)
Which obviously always outputs (0, state). I do know why it does that and I know that my algorithm is wrong but I don't know how to write it so it does what I want. I would be forever grateful :-) if you could bring me up to speed.
Thank you so much! Carina