A fast algorithm for solving linearly recurrent sequences

Abstract

We present an algorithm which computes the $D^{th}$ term of a sequence satisfying a linear recurrence relation of order $d$ over a field $K$ in $O(\mathsf{M}(\bar{d})\log (D)+\mathsf{M}(d)\log (d))$ operations in $K$, where $\bar{d}\le d$ is the degree of the squarefree part of the annihilating polynomial of the recurrence and $\mathsf{M}$ is the cost of polynomial multiplication in $K$. This is a refinement of the previously optimal result of $O(\mathsf{M}(d)\log (D))$ operations, due to Fiduccia.

ISSAC 2018 poster abstract