A fast algorithm for solving linearly recurrent sequences
Seung Gyu Hyun, Stephen Melczer, Catherine St-Pierre · ACM communications in computer algebra · 2019
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 (M(d̄) log( D ) + M( d ) log( d )) operations in K, where d̄ ≤ d is the degree of the squarefree part of the annihilating polynomial of the recurrence and M is the cost of polynomial multiplication in K. This is a refinement of the previously optimal result of O (M( d ) log( D )) operations, due to Fiduccia.