LFSR 的配置文件複雜性

我試圖了解如何計算 LFSR 的線性複雜度曲線。

例如，我有位序列 $ 110101 $ 及其簡介 $ 1 1 2 2 3 3 $ .

有沒有簡單的方法來生成配置文件？

鑑於任何 $ n- $ 位序列 $ (a_1,\ldots,a_n) $ 和 $ a_k \in {0,1} $ 您可以使用 Berlekamp Massey 算法（方便遞歸）來獲得最小度特徵多項式 $ C_m(X) $ 在哪裡 $ C_m(X) $ 是 Berlekamp Massey 的輸出多項式，當其輸入為 $ (a_0,\ldots,a_m) $ 和 $ 1\leq m\leq n. $

的線性複雜度曲線 $ (a_1,\ldots,a_n) $ 只是序列 $ d_1,\ldots,d_n $ 在哪裡 $ d_m $ 是程度 $ C_m(X) $ .

如果你有 $ n=2^k, $ 那麼有一個更快的算法來計算 $ d_n $ 由於 Richard Games 和 Agnes Chan，所謂的 Chan-Games 算法，當然可以用來獲得 $ d_1,d_2,d_{2^2},\ldots,d_{2^k} $ 但不是完整的個人資料。這具有復雜性 $ O(n \log n) $ 而 Berlekamp Massey 具有復雜性 $ O(n^2). $

對於案例，還有其他快速算法，例如 $ n=m 2^k $ 在哪裡 $ m $ 奇怪的是，它使用了編碼理論結果的各種推廣，也稱為 Blahut 定理，即序列的線性複雜度是序列的適當定義和正規化的有限傅立葉變換的漢明權重。

可以使用Berlekamp-Massey算法

引用自：https://crypto.stackexchange.com/questions/29676