Stream-Cipher
快速確定 LFSR 相位？
我知道可以從 LFSR 的輸出位向後工作，以 O(n) 的方式確定其回饋多項式。我也很好奇，給定一個 LFSR 狀態和多項式，是否有可能快速計算出 LFSR 狀態與給定紀元狀態（例如：全一狀態）之間的距離。我知道的唯一可靠的方法是向前/向後執行 LFSR 直到狀態為紀元狀態並使用計數器跟踪。
編輯：多考慮一下，這相當於解決 $ S = M^NE $ 迅速地 $ N $ ， 在哪裡 $ S $ 是你現在的狀態， $ E $ 是紀元狀態並且 $ M $ 是 LFSR 的伴隨矩陣。任何人都可以快速解決環中的離散對數問題 $ KxK $ $ GF(2) $ 矩陣？
好吧，看待這個問題的一種方法是注意到，如果回饋多項式是素數，那麼從狀態開始的結果 $ E $ ，然後將 LFSR 向前推進 $ N $ 步驟是價值 $ 2^N \cdot E $ , 我們在哪裡進行計算 $ GF(2^K) $ ，使用多項式表示（回饋多項式是多項式）。此外，我相信如果回饋多項式不是素數，那麼可以將該多項式分解為其素數，以每個素數為模求解等效解，然後重新組合它們。
所以，解決尋找問題 $ N $ 相當於解決 $ S = 2^N \cdot E $ 在 $ GF(2^K) $ ，或者換句話說， $ S/E = 2^N $ ; 也就是說，這個問題可以簡化為解決離散對數問題 $ GF(2^K) $ .
對問題的重新措辭能給我們帶來什麼？好吧，事實證明，這方面最近有成果；本文向我們展示瞭如何在“準多項式”時間內解決這個問題（他們的意思是 $ K^{O(\log K)} $ ; 技術上是超多項式，但只是勉強）；那篇論文告訴我們如何在小特徵欄位上快速做離散對數，並且特徵 2 盡可能小。