Revision history [back]
 | 1 | initial version |
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.
