Score:1

Polynomial notation of LFSR

se flag

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?

kelalaka avatar
in flag
[Visual guide](https://crypto.stackexchange.com/a/89829/18298) and $P(x) = 0$ as usual!
Fractalice avatar
in flag
By the way, generating functions in combinatorics are based on the same idea.
Score:3
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.