Lfsr
上限線性回饋移位寄存器
很明顯，當我們有任何輸出流時 $ x_0,x_1,… $ 由線性回饋移位寄存器產生，那麼這個輸出必須是周期性的。
現在我想知道我們是否可以從線性回饋移位寄存器中找到輸出序列週期的上限 $ R $ 註冊結束 $ \mathbb F_q $ ?
在他們之間，KG和Dilip Sarwate幾乎回答了你的問題。也就是說，您可以使用KG描述的方法得出一個上限：
當 LFSR 達到它之前的狀態時，輸出序列會發生什麼？有多少種可能的狀態？現在你有一個上限
但是，要弄清楚這個界限有多緊密可能要困難得多（根據Dilip 的評論）：
一般來說，多項式的周期 $ g(x) $ 是最小整數 $ e $ 這樣 $ g(x) $ 劃分 $ x^e−1 $ . 如果 $ g(x) $ 是 LFSR 的回饋多項式，則 $ e $ 是您尋求的上限。
特別是，如果您使用所有條目初始化 LFSR，則生成的循環 $ 0 $ 除了最後一個設置為 $ 1 $ .
對於良好的 LFSR，週期將接近可能的最大值。考慮 KG 描述的邊界的緊密性：如果回饋多項式選擇“糟糕”（例如 $ x^k-1 $ )，週期可能要短得多。
因為每次你“踩”LFSR，你都會乘以 $ x $ 在適當的欄位擴展範圍內，計算週期無關緊要的周期開始。您的初始條件是否在此循環中的某個位置確實很重要，例如使用 $ 0 $ 狀態導致只有一個循環 $ 1 $ 元素。現在，如果週期最大，那麼每個非零元素都必須是“主”週期的一部分，因此任何初始化向量都會導致最大周期的 LFSR。但是，如果週期低於此值，我們必須小心確保起始向量確實在主週期上。