Identities for Linear Recurring Sequences
Library Home || Full Table of Contents || Suggest a Link || Library Help
|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.|
|Math Topics:||Sequences and Sets|
© 1994- The Math Forum at NCTM. All rights reserved.