Linear Complexity of Product of Two LFSRs

71 Views Asked by At

I'm trying to understand the proof of theorem 3.5 on page 67/68 in Andreas Klein's book on stream ciphers. It states that $\zeta_j^{(l)}$ are the roots of the polynomial $f^{(l)*}$, i.e. $f^{(l)}(z)= \prod_{k'=1}^{k_l}\prod_{j=1}^{n_{k'}}(1-z \zeta_j^{(l)})=\prod_{j=1}^{n_1^{(l)}}(1-z \zeta_j^{(l)})^{e_j^{(l)}}$

My first question is: Why are the $\zeta_j^{(l)}$ roots of both $f_l$ and $f_l^*$? Does one know that they are roots of unity?

My second question is: How can I deduce the feedback polynomial of the product stream from the closed form? And why is it the feedback polynomial of the minimal LFSR if all $\zeta_j^{(1)}\zeta_k^{(2)}$ are different?

My confusion stems from the fact that the notation for $f$ and $f^*$ seems to be slightly interchangeable throughout the book.