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`

.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.