非原始 lfsr 序列
給定一個非原始 LFSR 序列（即狀態數小於 $ 2^n - 1 $ ); 我們如何找出特徵多項式？Berlekamp-Massey 算法會在這種情況下工作嗎？
例如; 對於以下序列-
$$ 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1 $$ 重複週期是 $ 105 $ . 應用 Berlekamp-Massey 算法返回
$ X^7 + X^6 + X^5 + X^1 + 1 $
手動給我一個不同的答案。我哪裡錯了？
編輯
添加我手動執行的操作：
我找到了原始多項式並用 LCM 來確認 $ Berlekamp-Massey $ 輸出。
為了檢查，我將多項式表示為 $ 11100011 $ ; 取了序列的前七位並做了 $ and $ 多項式運算。拿走了 $ xor $ 輸出並將該輸出附加到初始 7 位並繼續。這是我為交叉檢查收到的答案所做的。在這裡我可能出錯了。
週期的二進制序列 $ 105 $ 將具有作為除數的特徵多項式 $ x^{105}-1 $ . 自從 $ x^{105}-1 $ 具有不可約度的因數 $ 12, 4, 3 $ ， 和 $ 1 $ ,可以有一個長度為 LFSR $ 4+3=7 $ 生成一個週期序列 $ 105 $ ，這正是這裡發生的事情。注意
$$ x^7+x^6+x^5+x+1 = (x^3+x+1)(x^4+x^3+1) $$ 在哪裡 $ x^3+x+1 $ 和 $ x^4+x^3+1 $ 是不可約的（實際上是原始的）度多項式 $ 3 $ 和 $ 4 $ . 單獨地，較短的 LFSR 會生成周期序列 $ 7 $ 和 $ 15 $ ：“產品”序列有句點 $ \operatorname{lcm}(7,15)=105 $ .
正確實施的 Berlekamp Massey 始終為周期性序列提供正確的線性複雜度。有一個很好的線上資源，岩漿計算器，它有一個實現，如果你想檢查你做錯了什麼。點擊手冊連結上的密碼學章節，並在最後一節下查看 Berlekamp-Massey 命令和如何呼叫它的範例（需要使用 GF(2) 作為您的欄位，如範例中所示）。
編輯：岩漿計算器確認了上面的多項式。