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,\ldots,N+n-1$ of an $n$th-order linear recurrence. Unlike Fiduccia's algorithm our approach uses certain formulas for modular polynomial squarings. 
Dmitry I. Khomovsky
math.NT math.RA