/!\ Warning: long post!
I would like to understand the link between the multiplication in dual of the polynomial basis and the Fibonacci LFSR. I found that things are 'mirrored' so far in their recurrence relation. Could you please help me understand it?
1) Preliminaries
As per Dilip's Sarwate comment, Fibonacci and Galois LFSRs with primitive feedback polynomial $p(x)$ are essentially the iterative multiplication of a state $s(x)$ by $\alpha$ in $GF(q^n)$, where $\alpha$ is a root of $p(x)$ and $q$ a prime. We choose $q=2$. For Galois LFSRs, the elements are represented in the polynomial basis denoted by $<\alpha_{0},\alpha_{1},\alpha_{2},\dots,\alpha_{n-1}> \: = \: <1,\alpha,\alpha^2,\dots,\alpha^{n-1}>$. And for Fibonacci LFSRs, the elements are represented in the dual of the polynomial basis denoted by $<\beta_{0},\beta_{1},\beta_{2},\dots,\beta_{n-1}>$.
2) Example in $GF(2^4)$
Let $p(x) = 1 + x^3 + x^4$ be the primitive feedback polynomial, which has a root $\alpha$. We want to multiply the initial state by $\alpha$ in the dual of the polynomial basis to compute the next state and find the output of the corresponding Fibonacci LFSR.
2.1) Compute the dual of the polynomial basis
We know that $Tr_{GF(2^4)/GF(2)} (\alpha) = \alpha + \alpha^2 + \alpha^{2^{2}} + \alpha^{2^{3}}$ and the dual basis $<\beta_{0},\beta_{1},\beta_{2}, \beta_{3}>$ satisfies: \begin{align} Tr(\alpha_{i} \beta_{j}) &= 1 \: \text{ if } \: i=j \: \text{, with } i,j \in \{0,1,2,3\},\\ Tr(\alpha_{i} \beta_{j}) &= 0 \: \text{ if } \: i \neq j \,. \end{align}
To find the dual basis easily, we can compute the matrix $A = (a_{i,j})^{3}_{i,j=0}$ such that $a_{i,j} = Tr(\alpha_{i} \alpha_{j})$. Then, we compute the matrix $B = A^{-1} = (b_{i,j})^{3}_{i,j=0}$ and $\beta_{j} = \sum_{i=0}^{3} b_{i,j} \alpha_{i}$. (See 8.18 in Finite Fields for Computer Scientists and Engineers.)
I find: \begin{align} Tr(\alpha_{0}) &= Tr(1)=0 \\ Tr(\alpha_{1}) &= Tr(\alpha)=1\\ Tr(\alpha_{2}) &= Tr(\alpha^2)=1\\ Tr(\alpha_{3}) &= Tr(\alpha^3)=1\\ Tr(\alpha_{4}) &= Tr(1+\alpha^3)=1\\ Tr(\alpha_{5}) &= Tr(1+\alpha+\alpha^3)=0\\ Tr(\alpha_{6}) &= Tr(1+\alpha+\alpha^2+\alpha^3)=1 \,. \end{align}
Therefore, we have: $$ A = Tr \begin{bmatrix} \alpha_{0} & \alpha_{1} & \alpha_{2} & \alpha_{3} \\ \alpha_{1} & \alpha_{2} & \alpha_{3} & \alpha_{4} \\ \alpha_{2} & \alpha_{3} & \alpha_{4} & \alpha_{5} \\ \alpha_{3} & \alpha_{4} & \alpha_{5} & \alpha_{6} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix} \,. $$
We compute the inverse of $A$: $$ B = A^{-1} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix} \,. $$ Thus, the dual of the polynomial basis is $<\beta_{0},\beta_{1},\beta_{2}, \beta_{3}> = <1+\alpha, 1+\alpha^2+\alpha^3,\alpha+\alpha^3,\alpha+\alpha^2>$.
2.2) Multiplication in the dual of the polynomial basis
(I try to clarify the notation as much as possible.)
Let $i$ be an index in $\{0,1,2,3\}$. First, let us find the representation of the initial state $s_{0} \in GF(2^4)$ in the dual basis, which we denote by $s^{*}_{0}$.
In the polynomial basis, $s_{0} = a_{0} \alpha_{0} + a_{1} \alpha_{1} + a_{2} \alpha_{2} + a_{3} \alpha_{3}$, with $a_{i} \in GF(2)$. Let us say that $s_{0} = a_{2} \alpha_{2}$ and $a_{2}=1$.
In the dual of the polynomial basis, $s^{*}_{0} = b_{0} \beta_{0} + b_{1} \beta_{1} + b_{2} \beta_{2} + b_{3} \beta_{3}$ with $b_{i} = Tr(s^{*}_{0} \alpha_{i}) \in GF(2)$. (If I am correct? See 8.23 and Example 8.6 of Finite Fields for Computer Scientists and Engineers).
We define the column vectors $\boldsymbol{b} = [b_{0},b_{1},b_{2},b_{3}]^{\intercal}$ and $\boldsymbol{a} = [a_{0},a_{1},a_{2},a_{3}]^{\intercal}$. We can find the coefficients $b_{i}$ by computing $\boldsymbol{b} = A. \boldsymbol{a}$. We have $\boldsymbol{b} =[1,1,1,0]^{\intercal}$ since $\boldsymbol{a} = [0,0,1,0]^{\intercal}$. Therefore, $s^{*}_{0} = \beta_{0} + \beta_{1} + \beta_{2}$. Since $b_{3} = 0$, the first bit of output of the Fibonacci LFSR is $0$.
For the following state, we multiply the current state by $\alpha$ in the dual of the polynomial basis. Now, we define in general a state $k \in \mathbb{N}$ such that $s^{*}_{k} = b_{0} \beta_{0} + b_{1} \beta_{1} + b_{2} \beta_{2} + b_{3} \beta_{3}$. We can find the coefficients $b^{\prime}_{i}$ of the next state $s^{*}_{k+1}$ with: \begin{align} b^{\prime}_{j} = (\alpha s^{*}_{k})_{j} &= Tr(\alpha s^{*}_{k} \alpha_{j}) = Tr(s^{*}_{k} \alpha_{j+1}) = b_{j+1} \text{ for } j \in \{0,1,2\}, \\ b^{\prime}_{3} = (\alpha s^{*}_{k})_{3} &= Tr(s^{*}_{k} \alpha_{4})\,. \end{align} In our example ($\alpha_{4} = \alpha_{0} + \alpha_{3}$), \begin{align} Tr(s^{*}_{k} \alpha_{4}) &= b_{0} \beta_{0} (\alpha_{0} + \alpha_{3}) + b_{1} \beta_{1} (\alpha_{0} + \alpha_{3}) + b_{2} \beta_{2} (\alpha_{0} + \alpha_{3}) + b_{3} \beta_{3} (\alpha_{0} + \alpha_{3}) \\ &= b_{0} \beta_{0} \alpha_{0} + b_{3} \beta_{3} \alpha_{3} \\ &= b_{0} + b_{3} \\ \end{align} that are the taps of the LFSR, the recurrence relation (which corresponds to the reflected characteristic polynomial $1+ \alpha + \alpha^4$?).
To sum up, we have: \begin{align} b^{\prime}_{j} &= b_{j+1} \text{ for } j \in \{0,1,2\},\\ b^{\prime}_{3} &= b_{0} + b_{3} \,. \end{align}
For our example with $s^{*}_0$, the outputs of the LFSR are: \begin{align} s^{*}_{0} &= 1.\beta_{0} + 1.\beta_{1} + 1.\beta_{2} + 0.\beta_{3} \: \rightarrow \: (1,1,1,0) \:\: \text{output } 0 \\ s^{*}_{1} &= 1.\beta_{0} + 1.\beta_{1} + 0.\beta_{2} + 1.\beta_{3} \: \rightarrow \:(1,1,0,1) \:\: \text{output } 1 \\ s^{*}_{2} &= 1.\beta_{0} + 0.\beta_{1} + 1.\beta_{2} + 0.\beta_{3} \: \rightarrow \:(1,0,1,0) \:\: \text{output } 0\\ s^{*}_{3} &= 0.\beta_{0} + 1.\beta_{1} + 0.\beta_{2} + 1.\beta_{3} \: \rightarrow \: (0,1,0,1) \:\: \text{output } 1\\ s^{*}_{4} &= 1.\beta_{0} + 0.\beta_{1} + 1.\beta_{2} + 1.\beta_{3} \: \rightarrow \: (1,0,1,1) \:\: \text{output } 1\\ s^{*}_{5} &= 0.\beta_{0} + 1.\beta_{1} + 1.\beta_{2} + 0.\beta_{3} \: \rightarrow \:(0,1,1,0) \:\: \text{output } 0 \end{align}
2.3) From other sources
However, I found online that the Fibonaci LFSR is defined differently (see the answer here), and provides different outputs than my example.
In $GF(2^4)$, for our example, it is defined by: \begin{align} b^{\prime}_{j} &= b_{j-1} \text{ for } j \in \{1,2,3\},\\ b^{\prime}_{0} &= b_{0} + b_{3} \: \text{ if we consider the feedback polynomial } \alpha^4+\alpha^3+1 \\ &= b_{0} + b_{1} \: \text{ if we consider the reflected feedback polynomial } \alpha^4+\alpha+1 \,. \end{align}
We then have for the non-reflected polynomial: \begin{align} \text{Initial state: } \: & 1.\beta_{0} + 1.\beta_{1} + 1.\beta_{2} + 0.\beta_{3} \: \rightarrow \: (1,1,1,0) \:\: \text{output } 0 \\ & 1.\beta_{0} + 1.\beta_{1} + 1.\beta_{2} + 1.\beta_{3} \: \rightarrow \: (1,1,1,1) \:\: \text{output } 1 \\ & 0.\beta_{0} + 1.\beta_{1} + 1.\beta_{2} + 1.\beta_{3} \: \rightarrow \: (0,1,1,1) \:\: \text{output } 1 \\ & 1.\beta_{0} + 0.\beta_{1} + 1.\beta_{2} + 1.\beta_{3} \: \rightarrow \: (1,0,1,1) \:\: \text{output } 1 \\ \text{etc. } \end{align} It is also not the same with the reflected polynomial.
What do I get wrong? How do I get different definitions?
EDIT: Clarify and simplify notation.
I think that I figured it out! There are some mistakes in my post.
First of all, we indeed have the following relations in the dual base: \begin{align} b^{\prime}_{j} &= b_{j+1} \text{ for } j \in \{0,1,2\},\\ b^{\prime}_{3} &= b_{0} + b_{3} \,, \end{align} but the output of the Fibonacci LFSR is $b_{0}$ for the $k$-th state and not $b_{3}$.
To illustrate it, I change the order of the coefficients from my example in 2.2) below to highlight it. Therefore, we have: \begin{align} s^{*}_{0} &= 0.\beta_{3} + 1.\beta_{2} + 1.\beta_{1} + 1.\beta_{0} \: \rightarrow \: (0,1,1,1) \:\: \text{output } 1 \\ s^{*}_{1} &= 1.\beta_{3} + 0.\beta_{2} + 1.\beta_{1} + 1.\beta_{0} \: \rightarrow \:(1,0,1,1) \:\: \text{output } 1 \\ s^{*}_{2} &= 0.\beta_{3} + 1.\beta_{2} + 0.\beta_{1} + 1.\beta_{0} \: \rightarrow \:(0,1,0,1) \:\: \text{output } 1\\ s^{*}_{3} &= 1.\beta_{3} + 0.\beta_{2} + 1.\beta_{1} + 0.\beta_{0} \: \rightarrow \:(1,0,1,0) \:\: \text{output } 0\\ \text{etc.} \end{align}
In the literature, the coefficients' order is usually reversed, and so is the recurrence relation (see 2.3 from the question). That confused me. The reason seems to better mirror the Galois LFSR?
Therefore, with the 'reverse' coefficient order as found online, we have $(b_{3}, b_{2}, b_{1}, b_{0}) = (b^{r}_{0}, b^{r}_{1}, b^{r}_{2}, b^{r}_{3})$ and $<\beta_{3}, \beta_{2}, \beta_{1}, \beta_{0}> = <\beta^{r}_{0}, \beta^{r}_{1}, \beta^{r}_{2}, \beta^{r}_{3}>$. The reverse recurrence relation is therefore: \begin{align} b^{\prime \,r}_{j} &= b^{r}_{j-1} \text{ for } j \in \{1,2,3\},\\ b^{\prime \, r}_{0} &= b^{r}_{0} + b^{r}_{3} \: \text{ if we consider the feedback polynomial } \alpha^4+\alpha^3+1 \,. \end{align}
We would then have as a 'mirrored' example: \begin{align} s^{*}_{0} &= 0.\beta^{r}_{0} + 1.\beta^{r}_{1} + 1.\beta^{r}_{2} + 1.\beta^{r}_{3} \: \rightarrow \: (0,1,1,1) \:\: \text{output } 1 \\ s^{*}_{1} &= 1.\beta^{r}_{0} + 0.\beta^{r}_{1} + 1.\beta^{r}_{2} + 1.\beta^{r}_{3} \: \rightarrow \:(1,0,1,1) \:\: \text{output } 1 \\ s^{*}_{2} &= 0.\beta^{r}_{0} + 1.\beta^{r}_{1} + 0.\beta^{r}_{2} + 1.\beta^{r}_{3} \: \rightarrow \:(0,1,0,1) \:\: \text{output } 1\\ s^{*}_{3} &= 1.\beta^{r}_{1} + 0.\beta^{r}_{1} + 1.\beta^{r}_{2} + 0.\beta^{r}_{3} \: \rightarrow \:(1,0,1,0) \:\: \text{output } 0\\ \text{etc.} \end{align}
Remark 1: I found usually online that they do not explicit state that their example and the recurrence relation operate in the dual of the polynomial basis (Wikipedia - Fibonacci LFSR, New Wave Instrument - Linear Feedback Shift Registers or Omnicalculator - LFSR).
Remark 2: in the scientific literature, they do not seem to reverse the order of the coefficients (Dual bases and bit-serial multiplication in $F_q^n$ or From Hardware to Software Synthesis of Linear Feedback Shift Registers).