# How to prove this LFSR equation?

I am having difficulty solving part (ii) of Excercise 5.17 from Becker's Cipher Systems.

Exercise 5.17 $\quad$If $f(x),g(x)$ are any two polynomials over $GF(2)$ with $f(0)=g(0)=1$ show that

(i) $\Omega(f)\cap\Omega(g)=\Omega((f,g))$

(ii) $\Omega(f)+\Omega(g)=\Omega([f,g])$.

It is easy to prove that $\Omega(f)+\Omega(g) \subseteq \Omega([f,g])$, but could I have some hints to prove $\Omega([f,g]) \subseteq \Omega(f)+\Omega(g)$?

-
What does $\Omega$ mean for polynomials over $GF(2)\hspace{.01 in}$? $\;$ – Ricky Demer Nov 20 '13 at 11:21
$\Omega(f)$ is the solution space of $f(x)$, i.e. if $f(x) = c_0 + c_1 x+\cdots+c_{n-1}x^{n-1}+x^n$ is characteristic polynomial of an LFSR ($c_i$'s are feedback coefficients) then $\Omega(f)$ is space of all sequences that are producible by that LFSR (for all possible initial states). – Mahdi Khosravi Nov 20 '13 at 11:58
I suggest you edit the question to include that information, to make this question self-contained, as well as to define the notation $(f,g)$ and $[f,g]$ for polynomials and $+$ for solution spaces. Also, I suggest you edit the question to show what you've tried so far and where you got stuck. – D.W. Nov 20 '13 at 20:26
Hint if you are doing this with power series: If you write $f(x)=u(x) w(x)$ and $g(x)=v(x) w(x)$, with $\gcd(u(x), v(x)) = 1$, then any polynomial $r(x)$ can be written as $s(x)u(x) + t(x)v(x)$ for some $s(x), t(x)$. This will allow you to write a certain product involving $r(x)$ as a sum of two products. – K.G. Nov 21 '13 at 10:52
@K.G.: Could you copy that to an answer? – figlesquidge Nov 21 '13 at 13:49

Background:

An infinite sequence $c_0,c_1,c_2,\dots$ is generated by a (linear feedback shift register (LFSR) with) polynomial $f(x) = \sum_{i=0}^n f_i x^i$ if for any $j$, $$\sum_{i=0}^n c_{j+i} f_{n-i} = 0 \text.$$

We can consider the sequence as a power series $\sum_{i=0}^{\infty} c_i x^i$. If we multiply this power series with the polynomial $f(x)$, we get $$f(x) \sum c_i x^i = c_0 f_0 + (c_0 f_1 + c_1 f_0)x + (c_0 f_2 + c_1 f_1 + c_2 f_0)x^2 + \dots$$ We get that the $(j+n)$th coefficient is $\sum_{i=0}^n c_{j+i} f_{n-i}$. Which means that the sequence $c_0,c_1,c_2,\dots$ is generated by $f(x)$ if and only if the product of $\sum c_i x^i$ and $f(x)$ is a polynomial of degree less than $f(x)$.

We denote the set of all sequences generated by $f(x)$ as $\Omega(f(x))$. If we consider $\Omega(f(x))$ as a set of power series, we find that $$\Omega(f(x)) = \left\{ \sum_{i=0}^{\infty} c_i x^i : \deg\left(f(x) \sum c_i x^i\right) < \deg f(x) \right\} \text.$$

If $f(0) \not= 0$, then $f(x)$ is invertible in the power series ring. This gives us a different characterization of $\Omega(f(x))$: $$\Omega(f(x)) = \{ f(x)^{-1} r(x) : \deg r(x) < \deg f(x) \}\text.$$ As you observe, it is now easy to prove that if $f(x)$ divides $h(x)$, then $\Omega(f(x)) \subseteq \Omega(h(x))$, since if $h(x) = v(x) f(x)$, then for any $r(x)$ with $\deg r(x) < \deg f(x)$, we have that $$f(x)^{-1} r(x) = f(x)^{-1} v(x)^{-1} v(x) r(x) = h(x)^{-1} v(x) r(x) \in \Omega(h(x)).$$ The fact that $\Omega(h(x))$ is closed under addition and scalar multiplication then implies that $\Omega(f(x)) + \Omega(g(x)) \subseteq \Omega(\mathrm{lcm}(f(x), g(x)))$.

Direct approach hint:

If you write $f(x)=u(x)w(x)$ and $g(x)=v(x)w(x)$, with $\gcd(u(x),v(x))=1$, then any polynomial $r(x)$ can be written as $s(x)u(x)+t(x)v(x)$ for some $s(x)$,$t(x)$. The trick is to ensure that $s(x)$ and $t(x)$ don't end up with too high degrees, so you can't use the obvious approach.

Indirect approach hint:

You can also consider the dimensions of the (finite!) vector spaces involved, which together with (i) should give you a proof. This approach is probably easier.

-