Ask Your Question

# Playing with LFSR in sage

asked 2015-03-25 15:11:12 -0500 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

## 2 answers

Sort by » oldest newest most voted

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


Instead you should do:

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

## Comments

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

Hey there,

thank you so much for your answer :-)

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

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.

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

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2015-03-25 15:11:12 -0500

Seen: 225 times

Last updated: Mar 26 '15