Multiplication of two LFSR

Question

Let $a_n$, and $b_n$ two sequences generated by two LFSR with connection polynomials $P$, and $Q$. How to show the sequence $(a_n \cdot b_n)$ can be generated by a LFSR wit connection polynomial of degree upper bounded by $\deg(P)\cdot \deg(Q)$?

Answer 1

TL;DR: It's complicated.

Intuitively, the idea that all roots of the two polynomials contribute to the linear complexity of the product sequence, which can sometimes result in very high linear complexity goes back to Key, I believe.

I provide a few relevant pointers below.

In Eurocrypt 93, Gottfert and Niederreiter (On the Linear Complexity of the Products of Shift-Register Sequences) proved the following result. The notation $\sigma \in M(f)$ means that the sequence $\sigma$ has minimal polynomial $f.$

The presentation is quite technical, and sometimes such product sequences can be zero! In the other direction, the linear complexity can be as high as the product of the linear complexities, instead of the sum:

So, the linear complexity can be as high as the product of the linear complexities (take $a=b=1$ below):

A version of this is due to Rueppel and Staffelbach, see here (a later version of this appeared in the IEEE transactions on information theory).

Answer 2

Suppose that we take the oldest component from our LFSRs as output so that our factor LFSRs can be expressed via $$\mathbf a_n:=\begin{pmatrix}a_n\\a_{n+1}\\\vdots\\a_{n+\deg P-1}\end{pmatrix}=A^n\begin{pmatrix}a_0\\a_{1}\\\vdots\\a_{\deg P-1}\end{pmatrix}$$ and $$\mathbf b_n:=\begin{pmatrix}b_n\\b_{n+1}\\\vdots\\b_{n+\deg Q-1}\end{pmatrix}=B^n\begin{pmatrix}b_0\\b_{1}\\\vdots\\b_{\deg Q-1}\end{pmatrix}$$ for the usual Fibonacci matrices $A$ and $B$ and the outputs at time $n$ are $(1,0,0\ldots,0)\cdot \mathbf a_n$ and $(1,0,0\ldots,0)\cdot \mathbf b_n$ respectively.

Then $$\mathbf a_n\otimes\mathbf b_n=(A\otimes B)^n (\mathbf a_0\otimes\mathbf b_0)$$ where $\otimes$ is the Kronecker product. Note that $a_n\cdot b_n$ is the output of the product register at time $n$. By systematising $A\otimes B$ to a Fibonacci matrix by change of basis we can therefore write $a_n\cdot b_n$ as the output of an LSFR of degree at most $(\deg P)(\deg Q)$. The systematisation uses column operations to put $A\otimes B$ into a Fibonacci form $$\begin{pmatrix}0&1&0&0&\ldots&0&0&0&\ldots &0\\ 0&0&1&0&\ldots &0&0&0&\ldots &0\\ 0&0&0&1&\ldots &0&0&0&\ldots &0\\ \vdots&\vdots&\vdots&&\ddots&\vdots&\vdots&\vdots &&0\\ 0&0&0&0&\ldots&1&0&0&\ldots &0\\ R_0&R_1&R_2&R_3&\ldots&R_{d-1}&0&0&\ldots&0\\ \vdots&\vdots&\vdots&\vdots&&\vdots&\vdots&\vdots &&\vdots\\ \end{pmatrix}$$ (the precise non-zero values after the $d$th row are unimportant provided that the right hand columns are zero). This is equivalent to noting that $a_n$ can be written as a linear combination of $a_0,\ldots, a_{\deg P-1}$ via Galois equations and $b_n$ can be written as a linear combination of $b_0,\ldots, b_{\deg Q-1}$ so that $a_nb_n$ can be written as a linear combination of $a_0b_0, a_1b_0,\ldots a_{\deg P-2}b_{\deg Q-1},a_{\deg P-1}b_{\deg Q-1}$. If $d$ is the rank of these linear combinations over all values of $n$ then we perform a change of basis and write $a_nb_n$ as a linear combination of $a_0b_0, a_1b_1,\ldots a_{d-1}b_{d-1}$.