Efficient computation of terms of linear recurrence sequences of any order

In this paper we give efficient algorithms for computing second-, third-, and fourth-order linear recurrences. We also present an algorithm scheme for computing terms with the indices $N,\dots ,N+n-1$ of an $n$th-order linear recurrence. Unlike Fiduccia’s algorithm our approach uses certain formulas for modular polynomial squarings.