  We present a simple and fast algorithm for computing the $N$-th term of a
given linearly recurrent sequence. Our new algorithm uses $O(\mathsf{M}(d) \log
N)$ arithmetic operations, where $d$ is the order of the recurrence, and
$\mathsf{M}(d)$ denotes the number of arithmetic operations for computing the
product of two polynomials of degree $d$. The state-of-the-art algorithm, due
to Charles Fiduccia (1985), has the same arithmetic complexity up to a constant
factor. Our algorithm is simpler, faster and obtained by a totally different
method. We also discuss several algorithmic applications, notably to polynomial
modular exponentiation, powering of matrices and high-order lifting.
