Find $F_{2^n}$ for polynomial time.

Question

You have the nonnegative integers $a_1, a_2, ..., a_k, F_1, F_2, ...,F_k$. Consider the sequence $F_n = a_1F_{n - 1} + a_2F_{n - 2} + ... + a_kF_{n - k}, \forall n > k$. Suggest a polynomial algorithm that computes the last $k$ digits of a $F_{2^n}$.

Answer 1

This is possible in $O(n)$ time with $O(k^2)$ space. Let $$A=\begin{pmatrix}a_1&a_2&a_3&\cdots&a_{k-1}&a_k\\1&0&0&\cdots&0&0\\0&1&0&\cdots &0& 0\\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&\cdots&1&0\end{pmatrix}$$ and $$\mathbf F_n=\begin{pmatrix}F_n\\F_{n-1}\\\vdots\\F_{n-k+1}\end{pmatrix}.$$ Then $\mathbf F_{n+1}=A\mathbf F_n$ and more generally $\mathbf F_{n+r}=A^r\mathbf F_n$. Now compute something like $A^{2^n}$ by repeated squaring.