## Identities for Linear Recurring Sequences

There are several methods for computing the Nth term (mod M) of a
linear recurring sequence of order d in log_2(N) steps, but most
such methods require d^2 full multiplications (mod M) per step.
The algorithm described below requires only d(d+1)/2 multiplications
per step.
The algorithm can be described in terms of the basis sequences B_j(k),
defined by
d-1
x^n = sum B_j(n) x^j mod f(x)
j=0
where f(x) is the characteristic polynomial of the recurrence. There
are several useful identities on these sequences. In particular
B_k(n1+n2+..+nt+d)
= B_k(a1+a2+..+at+d) B_a1(n1) B_a2(n2) ... B_at(nt)
where summation from 0 to d-1 is implied over each index a*.
NOTATION: Summation from 0 to d-1 is implied over any index that
appears both as a subscript and as an argument in a single
term.
For computing the Nth term of a linear recurrence (mod M), the most
useful special case of the above identity is
B_k(2n+r) = B_k(a1+a2+r) B_a1(n) B_a2(n)
where r is set to either 0 or 1 according to the binary bits of N.
Because of the symmetry of the right hand side, only d(d+1)/2 full
multiplications are required per step.
There is a nice relation between the basis sequences B and the
s(n) sequences (i.e., the sums of the nth powers of the roots of f).
Let {i,j,..,k} be any given permutation of the integers {1,2,..,t}
with the disjoint cyclic components c1, c2,..,cr. Then we have
r
B_a1(n1+ai) B_a2(n2+aj) ... B_at(nt+ak) = prod s( sum(n[q]) )
q=1
where sum(n[q]) denotes the sum over all the n'x' such that x is in cq.
In the most trivial case, this identity reduces to the fact that s(n)
is the "trace" (or "contraction") of the basis sequences
s(n) = B_a(n+a)
Of course, given the basis sequence elements, we can easily compute the
Nth terms of any linear recurring sequence (not just s(n) with the
characteristic polynomial f(x), since every such sequence is a linear
combination of the basis sequences.

Return to MathPages Main Menu