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?
Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials
polynomials;pseudo random generators
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).