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 \leq 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.
Categories: cs.SC math.CO