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>
{"ft_lang_label":"__label__en","ft_lang_prob":0.68593377,"math_prob":0.9907447,"size":1414,"snap":"2019-35-2019-39","text_gpt3_token_len":502,"char_repetition_ratio":0.13120568,"word_repetition_ratio":0.052287582,"special_character_ratio":0.37199435,"punctuation_ratio":0.14332248,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998535,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-09-18T14:08:43Z\",\"WARC-Record-ID\":\"<urn:uuid:80d9c2d0-7362-4be8-859a-0d81a440a226>\",\"Content-Length\":\"4135\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:07a0155a-555b-46f7-8461-d9628723d7ac>\",\"WARC-Concurrent-To\":\"<urn:uuid:f1ed2534-c343-41a5-b44c-0e92dc021ce2>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/feeds/question/49613\",\"WARC-Payload-Digest\":\"sha1:ECN7DJGEVU52FQQEKEMULY6VWNPH3OHX\",\"WARC-Block-Digest\":\"sha1:BHRNHFCGEV7MSGAFLQRVF2E5NPXNRRFM\",\"WARC-Identified-Payload-Type\":\"application/atom+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-39/CC-MAIN-2019-39_segments_1568514573289.83_warc_CC-MAIN-20190918131429-20190918153429-00003.warc.gz\"}"}