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 Nov 20 '13 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$ – Mahdi Khosravi Nov 20 '13 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. Nov 20 '13 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. Nov 21 '13 at 10:52
  • 1
    $\begingroup$ @K.G.: Could you copy that to an answer? $\endgroup$ – Cryptographeur Nov 21 '13 at 13:49


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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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