https://hal.inria.fr/hal-02917827v2Bostan, AlinAlinBostanSPECFUN - Symbolic Special Functions : Fast and Certified - Inria Saclay - Ile de France - Inria - Institut National de Recherche en Informatique et en AutomatiqueMori, RyuheiRyuheiMoriTITECH - Tokyo Institute of Technology [Tokyo]A Simple and Fast Algorithm for Computing the $N$-th Term of a Linearly Recurrent SequenceHAL CCSD2021Algebraic AlgorithmsComputational ComplexityLinearly Recurrent SequenceRational Power SeriesFast Fourier TransformAlgebraic Algorithms[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]Bostan, Alin - DÃ©cider l'irrationalitÃ© et la transcendance - - DeRerumNatura2019 - ANR-19-CE40-0018 - AAPG2019 - VALID - 2020-12-21 16:02:122023-03-15 08:56:162020-12-21 16:03:42enConference papershttps://hal.inria.fr/hal-02917827v1application/pdf2We 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 and powering of matrices.