Berlekamp-Massey 輸入序列長度
對於給定的周期長度序列 $ N $ 正在為其構造最小多項式。Berlekamp-Massey 算法是否採用 $ 2N $ ，即重複的輸入序列還是只是輸入序列本身？產生疑問是因為通過採用原始序列 $ S $ 長度 $ N $ , 和序列 $ S | S $ （連接）長度 $ 2N $ ，我發現最小多項式值發生了變化，但我無法理解為什麼最小多項式應該改變。
賢者數學
範例 1：
如果我認為序列是
s=0101110然後它重複。然後通過在 SageMath 中使用 Berlekamp–Massey 函式給出最小多項式$$ x^3+x+1 $$程式碼：
berlekamp_massey([GF(2)(0), 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0])（這裡我必須重複序列，因為長度必須是偶數）
範例 2：
如果我認為序列是
s=011101然後它重複然後通過在 SageMath 中使用 Berlekamp–Massey 函式給出最小多項式$$ x^3+x^2+1 $$程式碼：
berlekamp_massey([GF(2)(0), 1, 1, 1, 0, 1])（因為長度甚至是 berlekamp massey 函式都接受這個）
範例 3：
如果我認為序列是 s=011101 然後它重複；然後通過在 SageMath 中使用 Berlekamp–Massey 函式給出最小多項式$$ x^5+x^4+x^3+x^2+1 $$
程式碼：
berlekamp_massey([GF(2)(0), 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1])（這裡我特意重複了一遍）
所以，我的問題是如何使用 Berlekamp-Massey 函式實際計算 SageMath 中序列的線性複雜度？上述例子中哪些是正確的，哪些是不正確的？
一方面是，如果到目前為止計算的序列的遞歸 $ (s_t){t \geq 0} $ 是長度 $ L $ , 你確實需要等到觀察 $ 2L $ 符號來驗證到目前為止生成的 LFSR 是否確實有效。這是因為係數必須滿足矩陣方程 $$ \left[\begin{array}{ccccc} s_0 & s_1 & s_2 & \cdots & s{L-1} \ s_1 & s_2 & s_3 & \cdots & s_{L} \ & \vdots & & \vdots & \ s_{L-1} & s_{L} & s_{L+1} & \cdots & s_{2L-2} \ \end{array} \right] \left[ \begin{array}{c} c_L \ c_{L-1} \ \vdots \ c_1\end{array} \right]
\left[ \begin{array}{c} s_L \ s_{L+1} \ \vdots \ s_{2L-1}\end{array} \right] $$
在哪裡 $ c_1,\ldots,c_L $ 是特徵方程的係數，以便有效。
這是由於遞歸的重疊性質，它必須繼續保持直到最後一個符號 ( $ s_L $ ) 不再是矩陣方程的一部分。
我正在使用bma.bozhu.me的python程式碼（網站最近不工作（HTTP問題），等待了很長時間的答案..）
- 範例：重複序列 $ s=(0, 1, 0, 1, 1, 1, 0) $
seq = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0) (poly, span) = Berlekamp_Massey_algorithm(seq)輸出
輸入序列是 (0, 1, 0, 1, 1, 1, 0)。其特徵多項式為(x^3 + x^1 + 1)，線性跨度為3。 2. 範例：重複序列 $ s=(0, 1, 1, 1, 0, 1) $
seq = (0,1,1,1,0,1) (poly, span) = Berlekamp_Massey_algorithm(seq)輸入序列是 (0, 1, 1, 1, 0, 1)。其特徵多項式為(x^3 + x^2 + 1)，線性跨度為3。 3. 範例：重複序列 $ s=(0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1) $
seq = (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1) (poly, span) = Berlekamp_Massey_algorithm(seq)輸入序列是 (0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1)。其特徵多項式為(x^5 + x^4 + x^3 + x^2 + x^1 + 1)，線性跨度為5。
是的，這似乎有問題，但是，不是！
當 Belekamp-Massey 產生一個結果時，BM 產生一個最小多項式。這並不意味著它將匹配您的下一個輸入。
記住，一個長度為 $ L $ 可以生成一個週期性的長度序列 $ 2^L-1 $ ; 全部 $ L $ -length 二進製字元串，除了全零。所以，有學位 $ 3 $ 意味著，一個最大的 LFSR 可以生成一個大小的序列 $ 7 $ . 實際的周期序列是 $ (0, 1, 1, 1, 0, 1,0) $ 請注意，我們有除零之外的所有三元組。
可以有一個具有非原始多項式的 LFSR 可以產生您的序列；這不是 BM 的工作。
第三種情況也有類似的問題，留給讀者吧。
查看線性複雜度配置文件
著眼於序列隨機性的質量，還提出了線性複雜度配置文件。在這種情況下，給出一個序列並產生線性複雜度的輪廓。Rainer A. Rueppel *在流密碼的分析和設計中對此進行了廣泛的分析
PN 序列由 LFSR 生成，正如我們所見，LCP 沒有增長！（您的序列有 LCP 3 和 5）。拋硬幣是理解的關鍵；
- 當向 BM 提供新輸入時，如果目前階段可以產生它，則線性複雜度保持不變，否則調整線性複雜度以使產生的 LFST 也接受前一個和新的。
因此，BM 只對給定部分產生最短的 LFSR，並沒有說明下一個輸入將與目前的 LFSR 進行數學運算。
注意：似乎 SageMath 正在工作。
- Rainer A. Rueppel 是James L. Massey的學生。這似乎是 Springer 系列中第一本致力於密碼學的書。
