ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 26 Mar 2015 18:39:00 +0100Playing with LFSR in sagehttps://ask.sagemath.org/question/26331/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_feedback_shift_register)
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:
<pre>
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)
</pre>
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! CarinaWed, 25 Mar 2015 21:11:12 +0100https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/Answer by rws for <p>Hi there,</p>
<p>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 :-)</p>
<p>Let's say I have a 16 bit LFSR that is defined by the polynomial</p>
<p>poly = x^16 + x^14 + x^13 + x^11 + 1</p>
<p>(that's the Wikipedia polynomial from <a href="http://en.wikipedia.org/wiki/Linear_feedback_shift_register">http://en.wikipedia.org/wiki/Linear_f...</a>)</p>
<p>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>
<pre>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)
</pre>
<p>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.</p>
<p>Thank you so much! Carina</p>
https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?answer=26339#post-id-26339While you got already a good specific answer you might be interested in Sage's LFSR implementation, see http://sagemath.org/doc/reference/cryptography/sage/crypto/lfsr.html Thu, 26 Mar 2015 09:32:44 +0100https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?answer=26339#post-id-26339Answer by tmonteil for <p>Hi there,</p>
<p>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 :-)</p>
<p>Let's say I have a 16 bit LFSR that is defined by the polynomial</p>
<p>poly = x^16 + x^14 + x^13 + x^11 + 1</p>
<p>(that's the Wikipedia polynomial from <a href="http://en.wikipedia.org/wiki/Linear_feedback_shift_register">http://en.wikipedia.org/wiki/Linear_f...</a>)</p>
<p>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>
<pre>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)
</pre>
<p>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.</p>
<p>Thank you so much! Carina</p>
https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?answer=26336#post-id-26336Here 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`.
Thu, 26 Mar 2015 01:26:14 +0100https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?answer=26336#post-id-26336Comment by tmonteil for <p>Here are some bits to start thinking.</p>
<p>First, the polynomial should have coefficients in the field of two elements <code>GF(2)</code>. In this binary field, the addition correspond to the <code>xor</code> operation:</p>
<pre><code>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
</code></pre>
<p>and the multiplication corresponds to the <code>and</code> operation:</p>
<pre><code>sage: F(1) * F(1)
1
sage: F(1) * F(0)
0
sage: F(0) * F(1)
0
sage: F(0) * F(0)
0
</code></pre>
<p>When you write </p>
<pre><code>sage: poly = x^16 + x^14 + x^13 + x^11 + 1
</code></pre>
<p>you define a symbolic expression, such as <code>cos(x)</code> or <code>log(pi)</code> but you do not tell Sage that the coefficients belong to <code>GF(2)</code>, the field with two elements:</p>
<pre><code>sage: poly.parent()
Symbolic Ring
sage: cos(x).parent()
Symbolic Ring
</code></pre>
<p>Instead you should do:</p>
<pre><code>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)
</code></pre>
<p>Now, you have a polynomial with coefficients in <code>GF(2)</code>, as you can check:</p>
<pre><code>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
</code></pre>
<p>You can check that this polynomial is primitive:</p>
<pre><code>sage: poly.is_primitive()
True
</code></pre>
<p>and that it divides <code>x^(2^16-1)+1</code>:</p>
<pre><code>sage: poly.divides(x^(2^16-1)+1)
True
</code></pre>
<p>According to your links, both properties together imply that the period of the LFSR is <code>2^16-1=65535</code>.</p>
https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?comment=26350#post-id-26350Wtiring
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.Thu, 26 Mar 2015 18:39:00 +0100https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?comment=26350#post-id-26350Comment by carinachen for <p>Here are some bits to start thinking.</p>
<p>First, the polynomial should have coefficients in the field of two elements <code>GF(2)</code>. In this binary field, the addition correspond to the <code>xor</code> operation:</p>
<pre><code>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
</code></pre>
<p>and the multiplication corresponds to the <code>and</code> operation:</p>
<pre><code>sage: F(1) * F(1)
1
sage: F(1) * F(0)
0
sage: F(0) * F(1)
0
sage: F(0) * F(0)
0
</code></pre>
<p>When you write </p>
<pre><code>sage: poly = x^16 + x^14 + x^13 + x^11 + 1
</code></pre>
<p>you define a symbolic expression, such as <code>cos(x)</code> or <code>log(pi)</code> but you do not tell Sage that the coefficients belong to <code>GF(2)</code>, the field with two elements:</p>
<pre><code>sage: poly.parent()
Symbolic Ring
sage: cos(x).parent()
Symbolic Ring
</code></pre>
<p>Instead you should do:</p>
<pre><code>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)
</code></pre>
<p>Now, you have a polynomial with coefficients in <code>GF(2)</code>, as you can check:</p>
<pre><code>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
</code></pre>
<p>You can check that this polynomial is primitive:</p>
<pre><code>sage: poly.is_primitive()
True
</code></pre>
<p>and that it divides <code>x^(2^16-1)+1</code>:</p>
<pre><code>sage: poly.divides(x^(2^16-1)+1)
True
</code></pre>
<p>According to your links, both properties together imply that the period of the LFSR is <code>2^16-1=65535</code>.</p>
https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?comment=26338#post-id-26338Oooops 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! CarinaThu, 26 Mar 2015 08:24:04 +0100https://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/?comment=26338#post-id-26338