# Playing with LFSR in sage

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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

edit retag close merge delete

Sort by » oldest newest most voted

While you got already a good specific answer you might be interested in Sage's LFSR implementation, see http://sagemath.org/doc/reference/cry...

more

Here are some bits to start thinking.

First, the polynomial should have coefficients in the field of two elements GF(2). In this binary field, the addition correspond to the xor operation:

sage: F = GF(2)
sage: F(1) + F(1)
0
sage: F(1) + F(0)
1
sage: F(0) + F(1)
1
sage: F(0) + F(0)
0


and the multiplication corresponds to the and operation:

sage: F(1) * F(1)
1
sage: F(1) * F(0)
0
sage: F(0) * F(1)
0
sage: F(0) * F(0)
0


When you write

sage: poly = x^16 + x^14 + x^13 + x^11 + 1


you define a symbolic expression, such as cos(x) or log(pi) but you do not tell Sage that the coefficients belong to GF(2), the field with two elements:

sage: poly.parent()
Symbolic Ring
sage: cos(x).parent()
Symbolic Ring


sage: x = polygen(GF(2), 'x')
sage: poly = x^16 + x^14 + x^13 + x^11 + 1
sage: poly.parent()
Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)


Now, you have a polynomial with coefficients in GF(2), as you can check:

sage: poly + 1
x^16 + x^14 + x^13 + x^11
sage: poly + x
x^16 + x^14 + x^13 + x^11 + x + 1
sage: poly + x^11
x^16 + x^14 + x^13 + 1
sage: poly + poly
0


You can check that this polynomial is primitive:

sage: poly.is_primitive()
True


and that it divides x^(2^16-1)+1:

sage: poly.divides(x^(2^16-1)+1)
True


According to your links, both properties together imply that the period of the LFSR is 2^16-1=65535.

more

Oooops I accidantly posted this as an answer. Here it goes again:

Hey there,

Oh yes I forgot the most important line when I copy and pasted my code. I used

P.<x> = GF(2)[]

Is that the same effect as the definition you described or am I doing it wrong still?

I'm still not sure how I would get the feedback right. Yes the period should be 65535, this is correct. So basically I want to write some code which repeatedly divies and modulos some polynomials and outputs a 65535 bit sequence before it start over. But I'm still not sure how to start. Maybe there's another pointer?

Thank you so much for your help! Carina

( 2015-03-26 08:24:04 +0200 )edit

Wtiring

 sage: P.<x> = GF(2)[]


define both P as the polynomial ring over GF(2) and the indeterminate x as an element of P.

Writing

sage: x = polygen(GF(2), 'x')


defines the same indeterminate x, as you can see by typing:

sage: x.parent() == P
True


So this is the same effect and you were right.

( 2015-03-26 18:39:00 +0200 )edit