給定 2n 個（或更多）非連續密鑰流位，找到一個 LFSR
給定 2n 個（或更多）非連續密鑰流位，我如何計算 LFSR 的多項式和狀態？已知為 n 位。如果它們是連續的，我可以使用 Berlekamp-Massey 算法。
簡單範例：n 是 7，我知道密鑰流是 0…0…1…0…1…0…1…1…1…0。 ..1…0…1…0 其中 . 是一個未知位
任何解釋或參考帶有算法的論文或教科書將不勝感激。
我們得到了序列 $ b_i $ 為了 $ i $ 倍數 $ m>1 $ 和 $ 0\le i<2n,m $ .
- 如果所有給定的 $ b_i $ 是相同的，我們無法計算任何缺失 $ b_i $ （超出了瘋狂的猜測，他們都是 $ b_0 $ ）， 停止。
- 建立序列 $ 2n $ 已知位 $ c_j=b_{(j,m)} $ 和 $ 0\le j<2n $ .
- 使用 Berlekamp–Massey 求 LFSR（多項式 $ P $ 學位 $ k $ 和 $ k $ -bit 初始狀態）匹配 $ c_j $ .
- 找一些時期 $ p $ 的 $ c_j $ . 對於小學位 $ k $ ，我們可以模擬LFSR的操作，直到狀態重複（可以說 $ k\le40 $ 在 PC 上）或者我們可以使用baby-step/giant-step（可以說 $ k\le75 $ 在 PC 上，請參閱前一版本的最後一節）。但更一般地說，如果 $ P $ 分解為不可約多項式的乘積 $ k_r $ （因此與 $ k=\sum k_r $ )，那麼一個週期是 $ p=\prod(2^{k_r}-1) $ .
注意：對於大型多項式，我們仍然可以有效地計算 $ c_j $ 對於大任意 $ j $ （見這個），一旦我們有 $ P $ 和起始狀態。
- 如果 $ \gcd(m,p)=1 $ ， 然後 $ b_i $ 也有時期 $ p $ ， 因此 $ \forall j\in\Bbb N,\ c_j=b_{(j,m\bmod p)} $ ; 它遵循 $ \forall i\in\Bbb N, b_i=c_{(i,m^{-1}\bmod p)} $
筆記： $ m^{-1}\bmod p $ 只需要計算一次，例如使用半擴展歐幾里得算法。
注：與 $ p=\prod(2^{k_r}-1) $ 和 $ m $ 問題中的二的冪， $ \gcd(m,p)=1 $ 總是成立。如果 $ \gcd(m,p)\ne1 $ ，有可能找到一個更小的周期，通過因式分解 $ p $ 並迭代地去除那些留下週期的因素，直到找到最小的周期 $ p_\text{min} $ （這取決於不可約因素 $ P $ 是否原始，並且在起點上）。 $ \gcd(m,p_\text{min})=1 $ 無需猜測即可得出結論。
一次 $ 2k $ 連續的 $ b_j $ 找到，找到產生它們的 LFSR 的一個簡單選擇是再次使用 Berlekamp-Massey。LFSR 的初始狀態為 $ b_j $ （斐波那契形式）當然是第一個 $ k $ 位 $ b_i $ .
未涵蓋（尚未？）：多項式算術將允許直接導出 LFSR $ b_j $ 從一個為 $ c_j $ ; 並得出結論 $ \gcd(m,p_\text{min})\ne1 $ 和部分資訊 $ b_j $ 可用。