Lfsr
讓我直接計算nthnthn^{text{th}}LFSR 的狀態？
我有一個具有已知狀態和抽頭的大型線性回饋移位寄存器。
現在我想計算 LFSR 之後的狀態 $ n $ 迭代。
問題： $ n $ 是在順序 $ 2^{256} $ 所以只是暴力破解不是一種選擇。是否有一種算法或封閉形式的解決方案可以讓我直接計算 $ n^{\text{th}} $ 狀態？
如果初始狀態是 $ b_0,b_1,\dots,b_{k-1} $ 並且遞歸關係是 $ b_k = \sum_{i = 0}^{k-1} a_ib_i $ ，那麼線上性代數方面，我們有
$$ \begin{pmatrix} b_1 \ b_2 \ \vdots \ b_k \end{pmatrix} = U \begin{pmatrix} b_0 \ b_1 \ \vdots \ b_{k-1} \end{pmatrix}, $$ 更一般地說 $$ \begin{pmatrix} b_{n} \ b_{n+1} \ \vdots \ b_{n+k-1} \end{pmatrix} = U^n \begin{pmatrix} b_0 \ b_1 \ \vdots \ b_{k-1} \end{pmatrix}, $$ 當然在哪裡 $$ U = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \ 0 & 0 & 1 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & 0 & \cdots & 1 \ a_0 & a_1 & a_2 & \cdots & a_{k-1} \end{pmatrix}. $$ 和 $ U^n $ 可以通過標準求冪算法有效地計算。