# Feedback polynomial of 7-bit Linear Feedback Shift Register

My friend gave me a question to solve. The question he asked me was: the following sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I went through some lectures on LFSR on youtube. But still I am unable to solve this. Can anyone point out how to approach or crack this kind of question?

1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1

• Repetition length is 105 and there is no sequence of more than seven 1 or zeros. So 7 bits LFSR is possible. You can try all combinations with a small program (only 128 polynomials possible) and find the LFSRs with lenght 105. You will then have to find the initial value. Et voilà ! Commented Mar 13, 2016 at 15:12
• I am getting answer as x^7 + x^6 + x^5 + x^1 + 1. Is this right? Commented Mar 13, 2016 at 15:37
• Do not post the same question on multiple sites. And do not delete a question once it's been answered, that's rude towards the answerer. Commented Mar 14, 2016 at 0:07
• Also posted on Crypto.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Commented Mar 14, 2016 at 2:39

## 3 Answers

The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.

There is a comprehensive and excellent answer in this earlier “Cryptanalysis of Linear Feedback Shift Registers” question. Alternatively, if you know the order of the recurrence is $n$, you can solve a linear system of the form $$\left( \begin{array}{lllll} z_i & z_{i+1} & \cdots & z_{i+n-1} \\ z_{i+1} & z_{i+2} & \cdots & z_{i+n} \\ & & \vdots & & \\ z_{i+n} & z_{i+n+1} & \cdots & z_{i+2n-1} \\ \end{array} \right) \left( \begin{array}{c} c_n \\ c_{n-1}\\ \vdots\\ c_2\\ c_1 \end{array} \right) = \left( \begin{array}{c} z_{i+n}\\ z_{i+n+1}\\ \vdots\\ z_{i+2n}\\ \end{array} \right)$$ where $(z_t)_{t \geq 1}$ are the sequence bits, and $i\geq 1$. Here $c_i$ are the recurrence coefficients, to be determined. This should be done over $GF(2)$ i.e., with mod 2 arithmetic.

If the recurrence is order $n$ then $c_n=1.$ If the recurrence is of lower order the system becomes singular and you need to work with a smaller square left upper submatrix.

The polynomial you want is $1+c_1 x+\ldots+c_n x^n.$

Note that the matrix method is of higher complexity than the recursive Berlekamp Massey algorithm in the linked question.

Denote the sequence by $X_0,X_1,\ldots$. If the minimal polynomial is $x^7 + a_6 x^6 + \cdots + a_0 x^0$, then (by definition) for every $N$ it will hold that $X_{N+7} = a_6 X_{N+6} + \cdots + a_0 X_N$ (modulo 2). (Your definition may vary slightly.) Since the first few values are $1,0,0,0,1,0,1,0$, this implies that $0 = a_6 + a_4 + a_0$. Collect enough such equations and solve them to recover the minimal polynomial.

• Thats how I did it! and got this x^7 + x^6 + x^5 + x^1 + 1. Is this right??? Commented Mar 13, 2016 at 16:00
• I don't know, but I count on you to have solved the equations correctly. Commented Mar 13, 2016 at 16:01
• CAn you please verify it?? is there any pre made tool to verify online??? Commented Mar 13, 2016 at 16:02
• No, I can't verify it. This is your TA's task. Commented Mar 13, 2016 at 16:02
• Perhaps, but if so, I'm sure you can find them on your own. Commented Mar 13, 2016 at 16:03