# Finding the polynomial for LFSR given it's length and output

Let's say that i know that the output of an LFSR with length 4 is 1,1,1,0,0,1,1. Constructing the 3 equations modulo 2: $$s_{4} = \sum\limits_{i=1}^{4}c_{i}s_{4-i} \Leftrightarrow c_{2}+c_{3}+c_{4}=0$$ $$s_{5} = \sum\limits_{i=1}^{4}c_{i}s_{5-i} \Leftrightarrow c_{3}+c_{4}=1$$ $$s_{6} = \sum\limits_{i=1}^{4}c_{i}s_{6-i} \Leftrightarrow c_{1}+c_{4}=1$$ Therefore, $$c_{2}=1, c_{1}=c_{3}$$ and $$c_{4}\neq c_{1}$$. So i came up with two polynomials for it: $$C(D) = 1+x^{2}+x^{4}$$ or $$C(D)=1+x+x^{2}+x^{3}$$. I used the berlekamp-massey algorithm and the minimal polynomial that came up for that initial sequence was the $$C(D)=1+x^{2}+x^{4}$$. I am confused because the polynomial $$C(D)=1+x+x^{2}+x^{3}$$ outputs the sequence too and it has lower degree than the one that B-M algorithm finds as minimal. Why is that? What condition am i missing?

• Can you expand on why your think that polynomial $C(D)=1+x+x^2+x^3$ outputs the sequence $1,1,1,0,0,1,1$? I suspect that statement is false.
– fgrieu
Dec 18, 2023 at 17:46
• $$s_{4} = c_{1} \cdot s_{3}+c_{2} \cdot s_{2}+c_{3} \cdot s_{1}+c_{4} \cdot s_{0}=1 \cdot 0+1 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 \equiv 0 \pmod2\\s_{5} = c_{1} \cdot s_{4}+c_{2} \cdot s_{3}+c_{3} \cdot s_{2}+c_{4} \cdot s_{1}=1 \cdot 0+1 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 \equiv 1 \pmod2\\s_{6} = c_{1} \cdot s_{5}+c_{2} \cdot s_{4}+c_{3} \cdot s_{3}+c_{4} \cdot s_{2}=1 \cdot 1+1 \cdot 0 + 1 \cdot 0 + 0 \cdot 1 \equiv 1 \pmod2$$ Dec 18, 2023 at 17:50

To ensure uniqueness you need to have more samples. Namely if the sequence segment is less than twice the LFSR length, the LFSR is not unique.

The BMA runs to generate the shortest unique LFSR given the input. Since you have 7 bits and $$2\times 3 < 7< 2\times 4$$ length 3 is the longest unique generator for this segment.

• Shouldn't the bma return the third degree polynomial then ? Dec 18, 2023 at 17:45
• @Prothean: yes it should, if there was a third degree polynomial that generates the sequence. But if there's one, it's not $C(D)=1+x+x^2+x^3$ by any convention that I have seen used.
– fgrieu
Dec 18, 2023 at 17:48

The question is correct when it remarks that the Berlekamp-Massey algorithm always outputs a minimal-degree polynomial for a given input sequence, thus something is at odds.

Problem is that the question's equations are for a degree-4 polynomial, therefore with $$c_4=1$$ (by the conventions generally used by courses that cover the Berlekamp-Massey algorithm). The solution $$C(D)=1+x+x^2+x^3$$ matches all the equations, but does so with $$c_4=0$$, thus is not valid (by said conventions). If we add $$c_4=1$$ in the constraints and solve the system of equations, then we get $$1+x^2+x^4$$ as in Berlekamp-Massey.

Another way to look at it is that $$C(D)=1+x+x^2+x^3$$ has degree 3, thus (at least stated without a LFSR size mentionned) should be able to predict the fourth output $$s_3$$ from the first three ones $$s_0$$ $$s_1$$ $$s_2$$ per the equation $$s_3=\displaystyle\sum_{i=1}^3c_i\,s_{3-i}$$, but is not.

Yet another way is seeing that with the question's equations and $$c_4=0$$, bit $$s_0$$ is ignored, thus has no effect on future outputs, thus is wasting an LFSR stage.

From a "get the maximum points" perspective:

• If the question does not state that the LFSR size is 4 (including if it states that the LFSR size is at most 4 or at least 4) and does not ask for the LFSR size, then $$1+x^2+x^4$$ is correct, and $$1+x+x^2+x^3$$ without mention of an LFSR size is not, even if the wording of the question allows for multiple polynomials.
• If the question asks for a single polynomial and states that the LFSR size is 4, then $$1+x^2+x^4$$ is the best bet, because it follows the most usual convention that the degree of the polynomial is the LFSR size.
• If the question explicitly allows multiple polynomials, and states that the LFSR size is 4, then $$1+x^2+x^4$$ must be given, and $$1+x+x^2+x^3$$ can arguably be.
• First of all thank you for the answer, i don't know a lot about cryptography so forgive my ignorance. If we know that lfs'r length is 4 do we instantly get that $c_{4} = 1$ ? I mean the question gives me the first 7 bits and the length (4), so there are 2 polynomials that can be the connection polynomials for that lfsr ? Dec 18, 2023 at 18:26
• @Prothean: yes with the convention used in the context of the Berlekamp-Massey algorithm, or any convention where the degree of the polynomial is assumed to tell (or otherwise always match) the LFSR's length. But conventions vary.
– fgrieu
Dec 18, 2023 at 18:38