Berlekamp-Massey 的 LFSR 輸出採樣
查看在密碼算法中線性回饋移位寄存器的使用，我了解到Berlekamp-Massey 算法可用於找到生成給定序列的（最短）LFSR。
但我不確定我是否真的理解正確。
由於 LFSR 函式總是返回其（目前）狀態的副本，因此只需收集足夠的輸出即可構造一個 LFSR，該 LFSR 產生與被攻擊 LFSR 產生的二進制序列相同的二進制序列。從某種意義上說，這可以解釋為“收集足夠的樣本/輸出”，以便能夠創建一個允許重建相同二進制序列的函式。（希望到目前為止這是正確的嗎？）
現在，我不確定的是：
- Berlekamp-Massey 的正確 LFSR 輸出採樣
為了能夠成功應用 Berlekamp-Massey 算法，收集的樣本/輸出是*“按順序”收集的，還是“隨機抽樣”*就足夠了？
不同的詢問（以確保您得到我要詢問的內容），以下哪一項是正確的：
- 首先獲取一個隨機輸出並繼續收集幾個後續輸出，直到收集到足夠的輸出/樣本。（我稱之為*“按順序”*）
- 在採樣期間跳過/遺漏一些輸出並不代表問題，因為它不一定是一系列後續輸出；只要收集的隨機樣本/輸出的總數足夠。（我稱之為*“隨機抽樣”*）
- 期望資訊能夠計算所需樣本的最小數量
我見過一些似乎指向計算的公式，但我對它們的理解還不夠好，無法推斷出以下問題的答案：可以從單個 LFSR 樣本中扣除最小數量的待收集樣本/輸出，還是需要多個樣本/輸出來計算要收集的樣本/輸出的最小數量（成功應用 Berlekamp-Massey 算法所需的）？
請不要誤解我的問題。我正在“做我的研究”並且我一直在閱讀我發現的與 Berlekamp-Massey 相關的大量學術論文，但這並不意味著我有信心正確解釋這些論文。此外，搜尋引擎並不總是找到好的參考資料的最佳位置。如果您知道我絕對應該閱讀的特定論文（與 Berlekamp-Massey 和相關的 LFSR 攻擊/中斷有關），如果您能指出我將不勝感激。
Berlekamp-Massey 專為您觀察到的情況而設計 $ 2n $ 從一個連續的輸出位 $ n $ 位 LFSR。如果觀察到的位是隨機分散的，在流中隨機不連續的偏移量，它就不起作用。
資訊理論上，最少 $ 2n $ 需要輸出位來重建 LFSR。直覺地說，這是因為有 $ 2n $ 未知數：未知數 $ n $ LFSR 的位狀態，以及未知 $ n $ 抽頭上的位（回饋多項式）。因此，在您觀察連續輸出位的情況下，Berlekamp-Massey 完全符合已知的下限。
當然，您也可以使用線性代數來解決這些問題 $ 2n $ 未知數，但 Berlekamp-Massey 比求解線性方程組 ( $ O(n^2) $ 代替 $ O(n^3) $ ， 或類似的東西）。
您需要的觀察次數僅取決於 LFSR 的大小，而不取決於輸出位。如果您確實知道 LFSR 的大小，則無需查看任何輸出位即可預測需要多少輸出。如果您不知道 LFSR 的大小，那麼查看幾個輸出位並不能幫助您預測 LFSR 的大小，也不能幫助您預測需要多少輸出。
不過，關於 Berlekamp-Massey 的一件很酷的事情是，您不需要事先知道 LFSR 的大小（什麼 $ n $ 是）。您可以開始在輸出流上執行 Berlekamp-Massey，它將生成 LFSR 初始狀態和回饋多項式的候選。在每一位輸出之後，它將更新其候選者。一旦你觀察到 $ 2n $ 位輸出，您可以保證其候選者是正確的。如果你不知道什麼 $ n $ 也就是說，您可以選擇每個候選者並針對接下來的幾個輸出位對其進行測試；這將讓您辨識 Berlekamp-Massey 何時最終找到了合適的候選者，即，當您觀察到足夠的輸出流時（它會讓您辨識何時達到 $ 2n $ 限制，即使你不知道 $ n $ 第一的）。