Berlekamp-Massey 算法能否錯誤地檢測到 LFSR？

BMA 是否有可能從不是由 LFSR 生成的序列中檢測到不可約多項式？在假設它是由 LFSR 生成的情況下，我將一個序列輸入 BMA。它檢測到某個長度的多項式，但無法從該多項式重建序列。我不想假設 BMA 的實現有錯誤。如果在任何情況下都不能以“是”回答上述問題，則該實施一定是不正確的。

不。

給定一個任意長的序列 $ (x_1,\ldots,x_t,\ldots) $ 考慮它的初始部分。

任何（有限）序列$$ x^{(n)}:=(x_1,\ldots,x_n) $$可以由相同長度的循環 LFSR 生成。只需循環位，無需水龍頭。

如果不存在生成的較短 LFSR，BMA 將檢測到這一點 $ x^{(n)} $ . 並將收斂以正確檢測唯一生成的最短 LFSR $ x^{(n)} $ 如果你餵牠兩倍的初始位 $ x^{(2n)}. $

修復你的程式碼。

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