0
$\begingroup$

If the characteristical polynomial of LFSR is $P(x)=c_nx^n+c_{n-1}x^{n-1}+\dots+c_0x_0$, state is a polynomial $S(x)=s_{n-1}x^{n-1}+s_{n-2}x^{n-2}\dots+s_0x_0$ where $(s_0, s_1, ..., s_{n-1})$ is vector of initial values, then $S_i(x)= (x^i S(x)) \mathrm{mod} \,P(x)$. (https://crypto.stackexchange.com/a/15232)

But on the other hand, we can get vector of $S_i$ coefficient like this: $A^i\cdot v$, where $A$ is some matrix that is connected with characteristical polynomial and $v$ is vector that is connected with initial values.

What should be this matrix and vector in terms of $c_0, \dots, c_n$ and $s_0, \dots, s_{n-1}$? So, if we take the example from the link above, $S_0(x)=x^2$, $P(x)=x^4+x^3+1$, so

$S_1(x)=\big(x\cdot S_0(x)\big)\bmod P(x)=x^3$,

$S_2(x)=\big(x\cdot S_1(x)\big)\bmod P(x)=x^3+1$,

$S_3(x)=\big(x\cdot S_2(x)\big)\bmod P(x)=x^3+x+1$ etc.

So what should be $A$ and $v$ to get

$A\cdot v = (0,0,0,1)^T$,

$A^2\cdot v = (1,0,0,1)^T$,

$A^3\cdot v = (1, 1, 0, 1)^T$ etc.?

$\endgroup$

1 Answer 1

1
$\begingroup$

$$A=\begin{pmatrix} 0 & 0 & 0 & \cdots & -\frac{a_0}{a_n} \\ 1 & 0 & 0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & -\frac{a_1}{a_n}\\ 0 & 0 & \cdots & 0& -\frac{a_{n-2}}{a_n} \\ 0 & 0 & \cdots & 1 & -\frac{a_{n-1}}{a_n} \end{pmatrix},$$ $v=(s_0, s_1, \dots, s_{n-1})^T$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .