A fast algorithm for solving linearly recurrent sequences

Seung Gyu Hyun, Stephen Melczer, Catherine St-Pierre

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) + \mat…