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 log2(N) steps, but most such methods require d2 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 Bj(k), defined by



where f(x) is the characteristic polynomial of the recurrence. There are several useful identities involving these sequences. In particular, we have



where summation from 0 to d−1 is implied over each of the a indices.


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



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



In the most trivial case, this identity reduces to the fact that s(n) is the "trace" (or "contraction") of the basis sequences



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