Berlekamp-Massey 算法：序列長度小於 LFSR 長度兩倍的情況
假設我們有一個序列 $ N $ 由線性回饋移位寄存器 ( LFSR ) 產生的數字，並且最短的此類 LFSR 具有長度 $ L $ . Berlekamp-Massey 算法是流密碼（以及許多其他東西）密碼分析的一個非常重要的工具；如果 $ 2L\leq N $ , 該算法將產生唯一的最短 LFSR 長度 $ L $ 生成給定的序列。
我只是知道這是事實，但從未真正看過算法。現在我正在閱讀Massey 提出的算法的論文，我有點驚訝地意識到該算法在任何情況下都會返回所需的 LFSR，即使 $ 2L>N $ ，但是在這種情況下，我們沒有生成序列的唯一LFSR，但是 $ 2L-N $ 其中（在二進制情況下）。
那麼為什麼我們總是只在以下情況下才使用 Berlekamp-Massey 算法 $ 2L\leq N $ ? 實際上，什麼樣的長度 $ L $ 我們是否在密碼系統中使用，並且可以在什麼時候使用該算法 $ 2L>N $ 和 $ N $ 是“合理地”接近 $ 2L $ ? 或者在這種情況下算法是無用的嗎？
Berlekamp-Massey 算法找到可以產生給定序列的*最短LFSR。*形式上，如果序列有 $ n $ 元素 $ S_0, S_1, \ldots, S_{n-1} $ ，然後算法找到 $ \lambda_1, \lambda_2, \ldots, \lambda_t $ 這樣對於 $ i = t, t+1, \ldots, {n-1} $ ，以下等式成立：
$$ S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t = 0, \tag{1} $$ 那是， $$ S_i = -\bigr(S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t \bigr). \tag{2} $$ 請注意，對於 $ i=t $ ， 我們有 $$ S_{t} = -\bigr(S_{t-1}\lambda_{1} + S_{t-2}\lambda_2 + \cdots + S_{0}\lambda_t \bigr)\tag{3} $$ 這個想法是LFSR的初始載入是 $ (S_0, S_1, \ldots, S_{t-1}) $ ，以及LFSR 內容的加權和 $ (3) $ 當 LFSR 內容向左移動一位時，被回饋到移位寄存器的右端。因此，LFSR 的新狀態是 $ (S_1, S_2,\ldots, S_{t-1}, S_t) $ . 在以後的時鐘週期中，LFSR 將包含 $ (S_{i-t}, S_{i-t+1},\ldots, S_{i-1}) $ ，回饋將計算 $ S_i $ 如給出的 $ (2) $ 所以LFSR的新狀態是 $ (S_{i-t+1}, S_{i-t+2},\ldots, S_{i-1}, S_i) $ . LFSR的輸出是從左端掉下來的符號，因此是 $ S_0, S_1, \ldots, S_{n-1} $ . dsp.SE 讀者會認識到，如果我們定義多項式
$$ S(z) = S_0 +S_1z + \cdots + S_{n-1}z^{n-1}, ~~ \Lambda(z) = 1 + \lambda_1z + \cdots + \lambda_tz^t, $$ 然後左邊 $ (1) $ 是係數 $ z^i $ 在產品中 $ S(z)\Lambda(z) $ . 因此，產品 $ S(z)\Lambda(z) $ 不包含學位條款 $ t, t+1, \ldots, n-1 $ . 轉向手頭的問題，如果給定的序列實際上可以由長度為的 LFSR生成 $ L $ （在哪裡 $ L $ 是能夠生成的最短 LFSR 的長度 $ S(z) $ ）， 而如果 $ n \geq 2L $ ，然後 Berlekamp-Massey 算法將找到回饋係數 $ \lambda_1, \lambda_2, \lambda_L $ 一旦它檢查了第一個未知 LFSR $ 2L $ 條款 $ S_0, S_1, \ldots, S_{2L-1} $ 給定的序列。然後它將處理剩餘的條款 $ S_{2L}, S_{2L+1}, \ldots, S_{n-1} $ 序列，並且會發現它已經找到的相同 LFSR 也會生成這些剩餘的項。
重要的是要記住 Berlekamp-Massey 算法會找到最短的LFSR $ (S_0, S_1, \ldots, S_{n-1}) $ ，並且這個 LFSR 可能與實際用於生成的 LFSR 不同 $ (S_0, S_1, \ldots, S_{n-1}) $ . 可以通過帶有回饋多項式的 LFSR 生成的任何序列 $ \Lambda(z) $ 也可以通過帶有回饋多項式的（更長的）LFSR 生成 $ \Lambda(z)\Psi(z) $ ，並且 Berlekamp-Massey 算法將找到工作的最短移位寄存器。
如果什麼 $ L $ 是這樣的 $ 2L > N $ , 然後 Berlekamp-Massey 算法將找到最短的 LFSR 生成 $ (S_0, S_1, \ldots, S_{n-1}) $ . 這個 LFSR 的長度一般不會 $ L $ 並且其回饋係數通常與用於生成序列的實際 LFSR 的回饋係數不同。如果在以後的時間，條款 $ S_{n}, S_{n+1}, \ldots, S_{2L-1} $ 眾所周知，該算法將擴展 LFSR 並最終得出正確的答案，但目前，它只會找到將生成的最短 LFSR $ (S_0, S_1, \ldots, S_{n-1}) $ .
從廣義上講，序列複雜性的 Kolmogorov-Chaitin 理論認為，對於幾乎所有長度的序列 $ n $ , 能列印出序列的最短程序有長度 $ n+c $ 在哪裡 $ c $ 是一個常數。換句話說，對於大多數序列，除了簡單地將序列儲存在記憶體中並列印出來之外，沒有什麼可以讓您通過計算生成 序列的計算方法。因此，給定任意長度序列 $ n $ , Berlekamp-Massey 算法通常會找到一個長度為 $ n-1 $ 儲存第一個 $ n-1 $ 符號然後計算 $ S_{n-1} $ 通過 $ (2) $ 和 $ t = i = n-1 $ .
OP問題的答案
“…可以在什麼情況下使用該算法 $ 2L>N $ 和 $ N $ 是“合理地”接近 $ 2L $ ？”
就是算法可以用，它會找到最短的LFSR，會生成 $ (S_0, S_1, \ldots, S_{n-1}) $ ，但這個 LFSR 通常不會有長度 $ L $ 並且回饋多項式通常與長度的 LFSR 不同 $ L $ 已知會產生 $ (S_0, S_1, \ldots, S_{n-1}) $ .