 Ryuhei Mori

Ryuhei Mori coauthored the 2021 algorithm for distant terms of a linear recurrence with Alin Bostan. Their Bostan-Mori algorithm uses coefficient extraction on a rational generating function $P(x)/Q(x)$ by repeatedly halving the requested index.^[ref]

Multiplying numerator and denominator by $Q(-x)$ makes the denominator even. Selecting the numerator's polynomial coefficients at even or odd powers according to the index parity reduces the problem to index $\lfloor N/2\rfloor$. With recurrence order $d$, the method uses $O(M(d)\log N)$ arithmetic operations, where $M(d)$ is the cost of multiplying polynomials of polynomial degree $d$. This reaches a distant term without computing every preceding term.