Kitamasa algorithm
= Kitamasa algorithm
{c}
= Kitamasa's algorithm
{c}
{synonym}
The Kitamasa algorithm evaluates a term of an order-$d$ <linear recurrence> by reducing powers of $x$ modulo its <characteristic polynomial of a linear recurrence>. If the <recurrence relation> is $a_{n+d}=\sum_{j=0}^{d-1}c_j a_{n+j}$, reduce $x^N$ modulo $x^d-\sum_{j=0}^{d-1}c_jx^j$ by <exponentiation by squaring>; the resulting coefficients give $a_N$ as a <linear combination> of $a_0,\ldots,a_{d-1}$. Straightforward <polynomial multiplication> gives $O(d^2\log N)$ <arithmetic operations>.