# Why is the polynomial of an LFSR called so?

As far as I understand, the "polynomial" of the LFSR tells us the positions of the register where taps are situated.

However, the natural way to look at the positions would be to think of them as $x_1, x_2, x_3,\cdots$. But we instead identify them as powers of something and call them $x, x^2, x^3, \cdots$

My question is, what are they powers of? And why do we add a 1 to the polynomial?

• you mention taps, are you more interested in the mathematics or hardware implications? – b degnan Feb 14 '17 at 22:33
• I am interested in mathematical implications @b degnan – Agnishom Chattopadhyay Feb 15 '17 at 2:32
• Old, but see here: blog.fkraiem.org/2013/10/06/… (it requires some notion of linear algebra, which can be found in any standard text) – fkraiem Feb 15 '17 at 12:48

The polynomial $X^i$ is a delay operator, so formally $X^i(s_t)=s_{t-i}$.

It's also a linear operator so $X^i(a s_t)=a s_{t-i}$.

Let's apply this to the following simple LFSR in Fibonacci configuration

At each clock cycle, a new state $s_t$ is computed from delayed states $s_{t-1}$ and $s_{t-3}$, as $s_t=s_{t-1}+s_{t-3}$. That recurrence can be rewritten as $s_{t-3}+s_{t-1}-s_t=0$, and represented as the polynomial $X^3+X-1=0$ (the $1$ is a shorthand for $X^0$). In binary, both $+$ and $-$ are eXlusive-OR $\oplus$ and we write the polynomial modulo 2, as $X^3+X+1.$

Moreover, not only is there a one to one correspondence between recurrences (equivalently LFSRs) and polynomials, but the roots of the polynomial feature in the solutions, i.e., the sequence generated.

• Do the delay operator and XOR form a field? – Agnishom Chattopadhyay Feb 15 '17 at 2:33
• I'll clarify when I get some time, on the answer itself. – kodlu Feb 15 '17 at 5:46
• @fgrieu, I have no problem with you editing and improving this terse answer. Thank you. – kodlu Feb 15 '17 at 21:29

Assuming that you are not a mathematician, this is what I tell my engineers: What polynomials represent in the mathematical sense are "extension fields" of Galois Fields, which are modulo(2) fields of binary. The smallest prime field that exists is $GF(2)$, and then we represent the others as extension fields of $GF(2^m)$, where $m$ is the number of bits. Again, this is because these are binary fields. These powers represent bit values in the field.

From the practical sense, what is a reducible polynomial? Here is an example:

$x^4+ x^3+ x^1+ 1 =(x^2+ x^1+ 1)(x^2+ 1)$

This is reducible and thereby cannot be used to create a prime extension field. This is why we use irreducible polynomials. The polynomial for AES is

$P(x)=x^8+x^4+ x^3+ x^1+ 1$

Even though this field is not reducible, it still has that $+1$ on it. The short description for the 1 is from set theory, where all elements in a field must form a multiplicative group, and there must me the identity element. Primes can still be multiplied by 1 to get a prime number. The $+1$ is there for completeness and drops out if you do any binary addition between two polynomial values because $+1$ XOR $+1$ is $0$