如何將伽羅瓦 LFSR 轉換為斐波那契 LFSR？

我剛剛找到了 Galois 類型 LFSR 的序列輸出，見這裡。

現在我知道有一個斐波那契類型的 LFSR 能夠輸出相同的序列，但是我怎麼能找到這個 LFSR 的前六個狀態呢？

在這個答案中，我將考慮在這個問題中提到的 Galois LFSR：Sequence output by a Galois type LFSR見下圖。

首先我們假設 5 個位的位置從左到右編號：0 .. 4

伽羅瓦表示如下：

+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  v  |     |  v  |     |  v  |     |   |
+--->+  1  +---->+  0  +--+->+  0  +--+->+  0  +--+->+  0  +-------> ...
    |     |     |     |     |     |     |     |     |     |
    +-----+     +-----+     +-----+     +-----+     +-----+

如果我們將 LFSR 迭代 10 輪，我們會得到：

1 0 0 0 0 : initial state
0 1 0 0 0 -> 0
0 0 1 0 0 -> 0
0 0 0 1 0 -> 0
0 0 0 0 1 -> 0
1 0 1 1 1 -> 1

1 1 1 0 0 -> 1
0 1 1 1 0 -> 0
0 0 1 1 1 -> 0
1 0 1 0 0 -> 1
0 1 0 1 0 -> 0

現在假設我們有一個斐波那契 LFSR，但我們想知道水龍頭在哪裡。我們將迭代 lfsr 並用字母命名未知數。解決這個問題有兩個技巧：

• 一個字母被設置一次，以後不再修改（與伽羅瓦版本相反）
• 使用初始10000狀態將顯示水龍頭的位置。

所以我們有：

1 0 0 0 0 : initial state
a 1 0 0 0 -> 0            (i)
b a 1 0 0 -> 0
c b a 1 0 -> 0
d c b a 1 -> 0
e d c b a -> 1

然後我們可以解決它。

f e d c b -> a = 1

通過(i)，我們可以推斷出位置 0 對輸出的影響：所有其他位置都為空。

g f e d c -> b = 0 -> b

b如果1只有位置 0 有影響的話。因此位置 1 也會影響使其回到 0。

h g f e d -> c = 0

c如果0只有位置 0 和 1 有影響的話。位置 2 也影響使其回到0.

i h g f e -> d = 1

d是它應該是的值，因此位置 3 沒有影響。

j i h g f -> e = 0

e是它應該是有回饋的值。

如果我們在兩個模型上繼續接下來的 5 個輸出，我們將得到以下流：01111

總結 LFSR 的斐波那契表示如下：

+-------------+-----------+-----------+------------------------+
|             ^           ^           ^                        |
|    +-----+  |  +-----+  |  +-----+  |  +-----+     +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |     |     |   |
+--->+  1  +---->+  0  +---->+  0  +---->+  0  +---->+  0  +-------> ...
    |     |     |     |     |     |     |     |     |     |
    +-----+     +-----+     +-----+     +-----+     +-----+

這是一個小的python程式碼來檢查兩者之間的等價性。

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