LFSR 從特徵多項式中獲得輸出？
假設你有一個 LFSR 的特徵多項式：
$$ f(X) = X^4 + X^3 + 1 $$ 給定一些初始狀態，我如何使用這個函式 f 來獲得 LFSR 的輸出？
顯然，我可以基於該函式創建 LFSR 圖，因為該函式描述了“水龍頭”的位置（參見 .eg Wikipedia 文章http://en.wikipedia.org/wiki/LFSR）：
|----+--------+ | | | +-->[0][1][1][0]-->然後像這樣迭代計算：0,1,1,0,0,…（這裡的初始狀態如圖所示，0,1,1,0）。
我知道你也可以從等式中得到這個輸出：
$$ s_j \equiv c_1s_{j-1} + c_2s_{j-2} + \dots + c_2s_{j-2} \pmod 2 $$ 這與“手動”從圖表中計算得出的結果相同。
但是我的問題是如何從特徵多項式中得到這個。除了以這種方式描述抽頭之外，特徵多項式還有什麼目的？如果你給 f 一些任意的論點，你到底在做什麼？論證 X 是什麼？
我覺得這應該在一些我找不到的易於訪問的線上指南或教程中很好地涵蓋，但是我已經閱讀了一些這樣的文本並蒐索了更多，這對我來說仍然不清楚。
多項式的變數傳統上記為 $ x $ ， 不是 $ X $ ; 並且，在處理 LFSR 時，多項式很少被視為函式。因此，我將多項式重寫為 $ P(x)=x^4+x^3+1 $ , 多項式 $ n=4 $ .
這是一個多項式，係數在域中 $ \operatorname{GF}(2) $ , 也注意到 $ \mathbb Z_2 $ 或者 $ ({0,1},+,\cdot) $ [注：在 $ \operatorname{GF}(2) $ , $ 1+1=0 $ ， 和 $ - $ 是相同的 $ + $ ]。多項式的係數都是 $ 0 $ 或者 $ 1 $ ，並且未顯示：一個術語 $ x^j $ 當其係數為 $ 1 $ ，當其係數為時不存在 $ 0 $ . 在執行多項式算術時，除非另有說明，否則我們正在處理多項式，而不考慮其變數和結果的值和域。
LFSR的狀態是多項式 $ S(x) $ 係數在 $ \operatorname{GF}(2) $ 最多學位 $ n-1 $ , 但也可以認為是：
- 一個向量 $ n $ 位 $ (s_0,s_1,\dots,s_{n-1}) $ 是的係數 $ S $ 從常數項上升到高階項，即 $ S(x)=\sum_{j=0}^{n-1}s_j\cdot x^j $ 與約定 $ x^0=1 $ ;
- 整數 $ \hat S=\sum_{j=0}^{n-1}s_j\cdot 2^j $ ; 多項式的加法變為按位異或，多項式的乘法變為無進位乘法$$ performed as binary multiplication, but replacing additions with bitwise eXclusive-OR $$; 相同的整數可以定義為 $ \hat S=S(2) $ [注：這裡我們正在考慮 $ S $ 作為一個多項式函式 $ \mathbb Z $ ].
根據定義，LFSR的下一個狀態是多項式的多項式除法的餘數 $ x\cdot S(x) $ 由多項式 $ P(x) $ ， 著名的 $ \big(x\cdot S(x)\big)\bmod P(x) $ .
根據多項式除法的定義，多項式除法的餘數 $ T(x) $ 由非零多項式 $ P(x) $ 是多項式 $ R(x) $ 學位小於 $ P(x) $ 使得存在多項式 $ Q(x) $ 和 $ T(x)=P(x)\cdot Q(x)+R(x) $ .
在進入 LFSR 下一步的背景下， $ Q(x) $ 或者是 $ Q(x)=1 $ [什麼時候 $ S $ 有學位 $ n-1 $ ] 或者 $ Q(x)=0 $
$$ otherwise $$; 因此下一個狀態 $ \big(x\cdot S(x)\big)\bmod P(x) $ 或者是 $ x\cdot S(x)+P(x) $ [什麼時候 $ S $ 有學位 $ n-1 $ ] 或者 $ x\cdot S(x) $ $$ otherwise $$. 例如，如果 LFSR 的初始狀態是 $ S_0(x)=x^2 $ ,
- 第一個非初始狀態是 $ S_1(x)=\big(x\cdot S_0(x)\big)\bmod P(x)=\big(x\cdot x^2\big)\bmod P(x)=x^3\bmod P(x)=x^3 $ .
- 第二個非初始狀態是 $ S_2(x)=\big(x\cdot S_1(x)\big)\bmod P(x) $ 那是 $ \big(x\cdot x^3\big)\bmod P(x)=x^4\bmod P(x)=x^3+1 $ ，最後一步，因為 $ x^4=P(x)\cdot Q(x)+x^3+1 $ 和 $ Q(x)=1 $ ，我們可以得到 $ x^3+1 $ 作為 $ x^4+P(x)=x^4+x^4+x^3+1=x^3+1 $ .
- $ S_3(x)=\big(x\cdot S_2(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+1\big)\Big)\bmod P(x) $ 那是 $ \big(x^4+x\big)\bmod P(x)=x^4+x+P(x)=x^3+x+1 $ .
- $ S_4(x)=\big(x\cdot S_3(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x+1\big)\Big)\bmod P(x) $ 那是 $ \big(x^4+x^2+x\big)\bmod P(x)=x^4+x^2+x+P(x)=x^3+x^2+x+1 $ .
- $ S_5(x)=\big(x\cdot S_4(x)\big)\bmod P(x)=\Big(x\cdot\big(x^3+x^2+x+1\big)\Big)\bmod P(x) $ 那是 $ \big(x^4+x^3+x^2+x\big)\bmod P(x)=x^4+x^3+x^2+x+P(x)=x^2+x+1 $ .
- $ S_6(x)=\big(x\cdot S_5(x)\big)\bmod P(x)=\Big(x\cdot\big(x^2+x+1\big)\Big)\bmod P(x) $ 那是 $ \big(x^3+x^2+x\big)\bmod P(x)=x^3+x^2+x $ .
使用位向量或整數很容易執行相同的計算，這在大多數電腦程序中都是如此。對於整數，我們定義 $ \hat P=P(2) $ [那是 $ \hat P=\text{0x19} $ 跟我們 $ P(x) $ ]，以及下面的狀態 $ \hat S $ 和 $ 0\le \hat S<2^n $ 是 $ (2\cdot\hat S)\oplus \hat P $ 或者 $ 2\cdot\hat S $ 小於 [或者，等價地，小於 $ 2^n $ ]， 在哪裡 $ \oplus $ 是按位異或 [
^C 中的運算符]。LFSR輸出的一種常見定義是度項的係數 $ n-1 $ 在LFSR的狀態。當歸約多項式時，常數項也很流行 $ P(x) $ 有一個常數項，實際情況就是這樣。有時
$$ especially with the later convention $$，不考慮初始狀態。 在上面的例子中，LFSR的輸出[包括初始狀態 $ S_0(x)=x^2 $ ] 因此
$ 0 $ , $ 1 $ , $ 1 $ , $ 1 $ , $ 1 $ , $ 0 $ , $ 1 $ …
有時它被用作反射表示，其中狀態 $ S(x) $ 由整數表示 $ \check S=\sum_{j=0}^{n-1}s_j\cdot 2^{n-1-j}=2^{n-1}\cdot S(1/2) $ [注：這裡我們正在考慮 $ S $ 作為一個多項式函式 $ \mathbb Q $ ]。
這允許將輸出作為表示狀態的整數的低位 [而不是它的等級位 $ n-1 $ ，這可能不太容易隔離]；並且可以在沒有任何測試的情況下計算下一個狀態，至少對大小為無符號字使用通用運算符 $ n $ 位，使用 C 表達式
S = (S>>1) ^ (P & -(S&1))where
Pis $ \check P=\lfloor2^{n-1}\cdot\big(P(1/2)\big)\rfloor $ [那P是 $ 9 $ 跟我們 $ P(x) $ ] 並適合無符號單詞；>>是無符號右移 [>>>在 Java 中]；&是按位與；並且根據對無符號字的一元運算符的定義-，-U是無符號字，使得 和 的U和-U可以被不能表示為無符號字的 2 的最小冪整除[這是-使用二進制補碼的一元運算符的定義]。例如，從相同的 $ S_0(x)=x^2 $ 和
P_ $ 9 $ , 我們S取值 $ 2 $ , $ 1 $ , $ 9 $ , $ 13 $ , $ 15 $ , $ 14 $ , $ 7 $ ..S = (S>>1) ^ (P & -(S&1))重複應用時，輸出相同 $ 0 $ , $ 1 $ , $ 1 $ , $ 1 $ , $ 1 $ , $ 0 $ , $ 1 $ .. 獲得為S&1.如果我們能夠使用位向量或整數而不是多項式，為什麼我們還要使用多項式，即使在理論上也是如此？
一個重要的原因是 $ S_{i+1}=\big(x\cdot S_i(x)\big)\bmod P(x) $ 給 $ S_i=\big(x^i\cdot S_i(x)\big)\bmod P(x)=\Big(\big(x^i\bmod P(x)\big)\cdot S_i(x)\Big)\bmod P(x) $ ，這是計算 $ i^\text{th} $ 及時狀態 $ \mathcal O(\log i) $ 而不是 $ \mathcal O(i) $ ，並將生成器的周期與 $ P(x) $ .
問題中的示意圖（其中第一個
+讀取順序是一個 XOR 門，左側有輸出，其他任何一個+都只是一條線）起初似乎與這個答案中的上述內容不匹配，這適用於 -稱為LFSR 的伽羅瓦構造。該圖使用 LFSR 的斐波那契構造。這兩種結構給出相同的輸出，但從不同的狀態開始。度數的斐波那契 LFSR 的狀態 $ n $ [帶多項式 $ P(x) $ 有一個常數]是第一個 $ n $ 具有相同多項式的 Galois LFSR 輸出的位
$$ or that polynomial reflected, depending on definition of a Fibonacci LFSR $$. 有關兩種 LFSR 的門實現的漂亮示意圖，請參見此處。