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)$?

  • 3
    $\begingroup$ What does $\Omega$ mean for polynomials over $GF(2)\hspace{.01 in}$? $\;$ $\endgroup$
    – user991
    Commented Nov 20, 2013 at 11:21
  • 1
    $\begingroup$ $\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). $\endgroup$ Commented Nov 20, 2013 at 11:58
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Nov 20, 2013 at 20:26
  • $\begingroup$ 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. $\endgroup$
    – K.G.
    Commented Nov 21, 2013 at 10:52
  • 1
    $\begingroup$ @K.G.: Could you copy that to an answer? $\endgroup$ Commented Nov 21, 2013 at 13:49

1 Answer 1



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.