查找到給定次數的所有多項式以生成位序列

考慮以下位序列：

00100000110

使用 Berlekamp-Massey 算法，我們可以找到以下最小次數多項式：

$ P(x)=x^6 + x^5 + x^4 + 1 $

現在，有沒有辦法找到可以生成相同位序列的給定 8 次以下的所有多項式？

給定任何有限序列 $ (a_0,a_1,\ldots,a_{N-1}) $ 我們可能有興趣準確地生成該序列，或生成以該序列作為其起始位的最小度數（週期性）序列。

簡單來說，長度的循環移位寄存器 $ L $ ，最初由 $ (a_0,\ldots,a_{L-1}) $ , 將生成這個序列，通過實現遞歸

$$ x_{t}=x_{t-L},\quad t\geq L, $$ 即，給出特徵多項式 $ X^L+1. $

Berlekamp Massey (BM) 產生的多項式是與該初始段匹配的最小次數多項式。你的序列

$$ (a_0,\ldots,a_{10})=(00100000110) $$有長度 $ N=11 $ BM給了你學位 $ 6 $ 多項式。 一般來說，會有一組多項式可以生成一個初始段。如果最小遞歸（即生成您的序列的最小度多項式）具有度 $ n $ , $ 2n $ 需要位來唯一確定它。因此，要獲得生成序列的唯一 8 次多項式，需要 16 位。

如果指定少於 16 位，通常會得到多個生成多項式。您有 5 位“空閒”可以從 11 位變為 16 位，因此您最多可以獲得 32 個不同的多項式，對應於所有這些可能性，除非生成的多項式中有任何線性相關性。

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