World's most popular travel blog for travel bloggers.

# [Answers] Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials

, ,
Problem Detail:

I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials.

In particular, $f(x),g(x) \in GF(2)[x]$ are primitive polynomials of order $n$, and the characteristic polynomial of the LFSR is given by: $$c(x)=f(x)g(x).$$ What is the minimal period of any state of this LFSR, other than the all-zeros state?

I've tried to say that if $c(x)$ is a product of two primitives then it has a period of $$\pi=2^{2n}-1$$ but my math gets me to $$\pi =2^{n+1}-2$$ What did I do wrong?

The states of a LFSR with characteristic polynomial $p(x)$ correspond to elements of the multiplicative group of $GF(2)[x]/(p(x))$. The period of a LFSR state is the order of the corresponding group element. So, we can rephrase this as a group theory question, and use facts we know from group theory to answer the question.

The LFSR state with minimal period is exactly the group element $g \in G$ with minimal order, where here $G_c$ is the multiplicative group of $GF(2)[x]/(c(x))$.

The LFSR state with minimal period (other than the all-zeros state) is the group element with minimal order (other than the identity element).

Thus, to find the minimal period you want, you need to find the order of the minimal-order group element of $G_c$ (other than the identity element $1$).

Assuming $f,g$ have no common factor (i.e., $f\ne g$), the structure of $G_c$ is $G_c \cong G_f \times G_f$, where $G_f$ is the multiplicative group of $GF(2)[x]/(f(x))$ and $G_g$ is the multiplicative group of $GF(2)[x]/(g(x))$. This follows from an analog of the Chinese remainder theorem.

Let $g_1$ be the group element of minimal order in $G_f$, and $g_2$ the group element of minimal order in $G_g$. From what we know about the structure of $G_c$, the group element of minimal order in $G_c$ is either $(g_1,1)$ or $(1,g_2)$. So it suffices to find the group elements of minimal order in $G_f$ and $G_g$.

From the fact that $f$ and $g$ are primitive, we know that $G_f,G_g$ are cyclic groups of order $2^{n_f}-1$, $2^{n_g}-1$, respectively, where $n_f = \deg f$ and $n_g = \deg g$. Per Lagrange's theorem, we know that the divisors of $2^n-1$ correspond to the orders of the group elements of $G_f,G_g$.

Let $d_f$ be the smallest divisor of $2^{n_f}-1$ (such that $d_f>1$), and similarly for $d_g$. Then the group element of minimal order in $G_f$ will have order $d_f$, and the group element of minimal order in $G_g$ will have order $d_g$. It follows that the group element of minimal order in $G_c$ will have order $d=\min(d_f,d_g)$, and the LFSR state of minimal period will have period $d$.

So, the answer to your question is: the minimal period (other than the all-zeros state) is exactly $\min(d_f,d_g)$ where $d_f$ is the smallest divisor of $2^{\deg f}-1$ (other than 1) and $d_g$ is the smallest divisor of $2^{\deg g}-1$ (other than 1).