A term from recent terms
A linear recurrence defines each term as a fixed combination of a few previous terms, such as the Fibonacci rule where each value is the sum of the two before it. Iterating to a far term is slow when the index is enormous.
Matrix form
Pack the recent terms into a state vector and find a companion matrix that, when multiplied, shifts the window forward by one and produces the next term:
- The state holds the last few terms in order.
- The matrix encodes the recurrence coefficients in its top row.
- Multiplying by the matrix advances the recurrence one step.
Raising this matrix to the index with fast squaring then jumps to any term, so the work grows with the number of bits in the index rather than the index itself.
Faster polynomial method
A more advanced approach uses polynomial remainders modulo the recurrence's characteristic polynomial, reaching a term with fewer operations per step than full matrix products, useful when the recurrence depth is large.
Key idea
A linear recurrence becomes a companion matrix that shifts the term window, so raising that matrix to the index with fast squaring computes any far term in time scaling with the number of bits in the index.