I want to prove the following theorem in LFSR:

If $f(x)$ is a polynomial in $\text{GF}(2)$ with exponent $e$, which means $f(x) \mid x^e + 1$.

I want to prove that $e \le 2^n -1$.

I had some attempts in special case that $f(x)$ is irreducible polynomial: if we get the period as $p$ we can easily prove $e \le p$ and from $p \le 2^n - 1$. We can then conclude the desired result but only for the special case.

Let me explain the proof I know:

For the case $f(x)$ is irreducible: $S_1(x) = \sum_{i=0}^{p-1} s_i x^i$ and we know: $G(x) = \frac{S_1(x)}{1 + x^p}$, $G(x) = \frac{\emptyset(x)}{f^\ast(x)}$ from this we know that $\deg(\emptyset) < \deg(f)$, $\frac{\emptyset(x)}{f^\ast(x)} = \frac{S_1(x)}{1 + x^p}$ so we conclude $\emptyset(x)(1 + x^p) = f^\ast(x)S_1(x)$, $(\emptyset, f) = 1$ so we have $f(x) \mid (1 + x^p) \rightarrow e \le p$

and we thereachieve the desired result.

  • 1
    $\begingroup$ Suggestion: if $p(x)$ is not irreducible, then $p(x) = q_1(x) q_2(x) ... q_k(x)$ for some multiset of irreducible polynomials $q_1, q_2, ..., q_k$. Would that help? $\endgroup$
    – poncho
    Commented Apr 24 at 17:19
  • $\begingroup$ you've omitted the definition of $n$, is it the degree of the polynomial? $\endgroup$
    – kodlu
    Commented Apr 24 at 17:57
  • $\begingroup$ Yes, sorry I didn't notice. n is the degree of polynomial $\endgroup$ Commented Apr 24 at 18:04
  • $\begingroup$ poncho I guess your suggestion doesn't help. If you have any opinion I will acclaim $\endgroup$ Commented Apr 24 at 18:05


Your Answer

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

Browse other questions tagged or ask your own question.