# 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