反向斐波那契 LFSR 抽頭
在 Bruce Schneier 的經典著作《應用密碼學》（20 週年紀念版）中，有一個最大長度 LFSR 的插圖：
根據這本書，這個 LFSR 使用多項式中的抽頭序列 $ x^{32}+x^7+x^5+x^3+x^2+x+1 $ 這是最大長度。
但是，我在網上找到的大多數範例（例如Wikipedia）都會將移位寄存器位的編號從輸入增加到輸出（從左到右）——這可能只是一種不同的約定——但抽頭也是相反的。在這個數字上，這將轉化為點擊 $ {b_1,b_{26},b_{28},b_{30},b_{31},b_{32}} $ .
我通常更傾向於相信參考書而不是隨機的線上資源，但我發現了數量驚人的反例。水龍頭是否正確放置在上圖中？
上圖中的水龍頭是否正確放置？
沒有。這在第 375 頁的第二版勘誤表中得到了承認（AFAIK 20週年紀念版本質上是第二版，開頭有一點額外內容）。
我從多項式確定斐波那契 LFSR的硬體實現的首選方法：
- 使用與多項式次數一樣多的移位寄存器。
- 數字移位寄存器狀態位（內部 D 門的輸出）來自 $ 0 $ 對於輸出，到 $ n-1 $ ; 因此 $ n $ 移位寄存器的輸入。
- 異或位 $ i $ 從 $ 0 $ 至 $ n-1 $ 有其任期的移位寄存器 $ x^i $ 存在於多項式中¹ ( $ x^0 $ 是術語 $ 1 $ 多項式）。
- 對於加擾器配置中的 LFSR，另外對加擾器的輸入進行異或。
- 將 XOR 的結果饋送到移位寄存器的輸入端。
根據慣例，顯示的抽頭用於多項式 $ x^{32}+x^{31}+x^6+x^4+x^2+x+1 $ 或者它是反射多項式 $ x^{32}+x^{31}+x^{30}+x^{28}+x^{26}+x+1 $ . 這些不是原始的²，因此，顯示的 LFSR 序列不是最大長度。
LFSR 和 CRC 是一個在文獻和實現中存在許多錯誤的領域，以及一些合理的約定，特別是對於 Fibonacci LFSR：
- 多項式的低階係數在 LFSR 的輸出上並沒有普遍的共識。對於反射的初始狀態，使用其他約定¹會導致生成序列中位的順序在時間上的反射。
- 隔離 LFSR 的最常見約定是 LFSR 的輸出是移位寄存器的輸出，因此輸出的第一位與移位寄存器的初始狀態相匹配。但是基於 LFSR 的擾碼器的常見約定是輸出是移位寄存器的輸入，這減少了電信應用中的延遲。這抵消了生成的序列。
- 從輸出到輸入的移位寄存器/初始狀態的位數沒有統一的協議。這是最好的恕我直言，因為它與輸出位出現的順序相匹配，並且人們同意隨時間遞增地對這些進行編號。
- 從 0（如上述方法）或從 1（如問題圖）開始編號移位寄存器位沒有一致意見。生成序列中的輸出位也存在同樣的問題，我發現約定有所不同。
許多理論工作、高速硬體和軟體都使用Galois LFSR。相對一致的是，如果他們的 $ n $ -位多項式是 $ P(x) $ ，然後他們的狀態 $ S(x) $ 是一次多項式（最多） $ n-1 $ 狀態位編號從 $ 0 $ 至 $ n-1 $ 根據排名 $ S $ . 狀態從 $ S(x) $ 至 $ x^k,S(x)\bmod P(x) $ 後 $ k $ 腳步。祝你好運。
Galois LFSR 很容易在硬體和軟體中實現：
s = (s<<1)^(p&-(s>>(n-1))); // Galois LFSR, assuming s an unsigned exactly n-bit s = (s>>1)^(q&-(s&1)); // Galois LFSR, reflected, assuming s at least n-bit注意：
p多項式是在沒有高階項的情況下計算的 $ \mathbb Z $ 為了 $ x=2 $ .q是反映的多項式，然後在沒有它的高階項的情況下進行評估 $ \mathbb Z $ 為了 $ x=2 $ .帶有項的斐波那契 LFSR 的輸出序列 $ 1 $ 存在於它的多項式中的伽羅瓦 LFSR 與反射多項式（使用上面的約定）相匹配，並且對初始狀態進行了適當的調整（這取決於關於從何處提取輸出序列的約定）。
¹另一種可能性是對位進行異或 $ i $ 有他們的任期 $ x^{(n-i)} $ 當下。僅當術語 $ 1=x^0 $ 存在於多項式中，這對於實踐中使用的所有多項式、所有可約多項式以及所有原始多項式（即從非零初始狀態開始時生成最大長度序列的那些，並且輸入 $ 0 $ 如果在加擾器配置中）。生成的序列一般不一樣。
² 證明：每一個本原多項式都是不可約的，並且 $ x^{32}+x^{31}+x^6+x^4+x^2+x+1 $ 不是，因為它可以被 $ x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^4+x^3+1 $ . 多項式及其反射在原始性和不可約性方面具有相同的狀態。