# Connection of characteristic polynomial $P(x)$ of LFSR ($S_i(x)=(x^iS_0(x) \bmod P(x)$) and its matrix form

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.?

$$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$$.