# Polynomial notation of LFSR

I was following along with Christof Paar's lecture on Linear Feedback Shift Registers. He explains the structure coherently as a set of flip flops where the 'taps' are defined by a bit vector (0 for no tap on that flip flop, 1 for a tap on that flip flop). This makes perfect sense to me.

But then he brings up the point that people describe an LFSR not as a set of flip flops and a bit vector to define the taps, but as a polynomial equation.

I don't understand what this polynomial representation is trying to do.

P(x) = x^4 + x + 1 would represent a network of 4 flip flops, the right-most two being 'tapped' to XOR into the new bit.

What is the value P(x) supposed to be? In fact, I'm not even sure what the x value is. Further mysteries to me: (1) the far right flip flop is represented by 1. Is this shorthand for x^0 ? (2) the x^4 term.... the four flip-flops are labelled 0,1,2,3. So why a power-four term?

Makes me wonder if this 'equation' isn't really an equation you expect to emit a value to use, but some kind of hand-wavy way to just describe the architecture of a LFSR?

• Visual guide and $P(x) = 0$ as usual! Oct 4, 2021 at 13:52
• By the way, generating functions in combinatorics are based on the same idea. Oct 4, 2021 at 16:06

What is the value $$P(x)$$ supposed to be?

Nothing. We are interested in the coefficients of the polynomial $$P(x)$$, which are restricted to the Booleans $$\{0,1\}$$. These coefficients reflect the wiring of the LFSR. For other polynomials, they could reflect the state of the LFSR. We seldom¹ need to evaluate that polynomial $$P(x)$$, or other polynomials we use, for a particular value of $$x$$, or even specify the set $$x$$ belongs to. Think of $$x$$ as an unspecified variable, be it in integers $$\mathbb Z$$, rationals $$\mathbb Q$$, reals $$\mathbb R$$, complexes $$\mathbb C$$, as you see fit; and confidently perform arithmetic on such polynomials per the standard rules of algebra, modified by $$1+1=0$$ (equivalently, by reducing all coefficients of polynomials modulo $$2$$).

The far right flip flop is represented by $$1$$. Is this shorthand for $$x^0$$?

Yes. Another reason we write $$1$$ is to avoid having to define $$0^0$$.

The four flip-flops are labelled $$0,1,2,3$$. So why a power-four term?

The degree-four term is only in $$P(x)$$, which represents the wiring of the LFSR, not the state of it's flip-flops. When dealing with the state, it will be represented by a polynomial $$S(x)$$ of degree at most three.

Also: when we reduce any polynomial modulo the polynomial $$P(x)$$, the remainder $$S(x)$$ has degree strictly lower that $$P(x)$$, thus it's coefficients (typically a new state of the LFSR) fit the four flip-flops.

Yet another way to see it is that the term $$x^4$$ in $$P(x)$$ corresponds to the bit that gets out of the shift register when we shift by one bit (equivalently, multiply the state by $$x$$), while the other bits correspond to adjustments of the new states of each flip-flop.

Makes me wonder if this 'equation' isn't really an equation you expect to emit a value to use, but some kind of hand-wavy way to just describe the architecture of a LFSR?

Indeed, $$P(x)$$ is about the architecture of the LFSR. The representation as polynomial $$P(x)$$ for architecture and $$S(x)$$ for state is useful to establish properties of LFSRs. In particular, for a LFSR in Galois form, the state evolves per $$S_{i+1}(x)=S_i(x)\,x\bmod P(x)$$, from which it follows $$S_i(x)=S_0(x)\,x^i\bmod P(x)$$.

Note: here, $$\bmod$$ yields the remainder per polynomial division, again with coefficients in the Booleans.

¹ Exceptions: evaluation of $$P(x)$$ at $$x=1$$ in the Booleans, or $$x=2$$ for the integers, yield occasionally interesting values.