how to prove the periodity of an LFSR - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:08:43Z https://cs.stackexchange.com/feeds/question/49613 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/49613 2 how to prove the periodity of an LFSR user107761 https://cs.stackexchange.com/users/42390 2015-11-17T22:27:36Z 2015-11-18T08:37:18Z <p>everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's correctness? I've tried o prove it like that: given $c(x)$ the characteristic polynomial and $h(x)$ theinitial state polynomial, I'll denote the minimal period with $\pi$ then: $${h(x) \over c(x)}=G(x)= \sum^\infty_{k=0}a_kx^k=\sum^{\pi -1}_{k=0}a_kx^k(1+x^\pi+x^{2\pi}...)={\sum^{\pi -1}_{k=0}a_kx^k \over 1-x^\pi}$$ and I'm not sure where to go from here</p> https://cs.stackexchange.com/questions/49613/-/49626#49626 1 Answer by Yuval Filmus for how to prove the periodity of an LFSR Yuval Filmus https://cs.stackexchange.com/users/683 2015-11-18T08:27:42Z 2015-11-18T08:27:42Z <p>Hint: The LFSR changes its state by multiplying it by $x$ modulo $c(x)$. So if the initial state is $x_0$, the state after $t$ steps is $x_t \equiv x_0 x^t \pmod{c(x)}$. In particular, $x_t = x_0$ if $x_0 (x^t-1) \equiv 0 \pmod{c(x)}$.</p>