For any two positive integers x and y define F(x,y) = xy (mod x+y). Given two initial values x[0] and x[1] we can form a sequence using the recurrence x[n] = F( x[n-1] , x[n-2] )
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.