Calculating Lucas Sequences efficiently

Question

I'm implementing the p+1 factorization algorithm. For that I need to calculate elements of the lucas sequence which is defined by:

(1) x_0 = 1, x_1 = a
(2) x_n+l  =  2 * a * x_n - x_n-l

I implemented it (C#) recursively but it is inefficient for bigger indexes.

static BigInteger Lucas(BigInteger a, BigInteger Q, BigInteger N)
    {
        if (Q == 0)
            return 1;
        if (Q == 1)
            return a;
        else
            return (2 * a * Lucas(a, Q - 1, N) - Lucas(a, Q - 2, N)) % N;
    }

I also know

(3) x_2n = 2 * (x_n)^2 - 1
(4) x_2n+1 = 2 * x_n+1 * x_n - a
(5) x_k(n+1) = 2 * x_k * x_kn - x_k(n-1)

(3) and (4) should help to calculate bigger Qs. But I'm unsure how. Somehow with the binary form of Q I think.

Any help is appreciated.

Answer 1

Here one can see how to find Nth Fibbonaci number using matrix powering with matrix

      n
(1 1)
(1 0)

You may exploit this approach to calculate Lucas numbers, using matrix (for your case x_n+l = 2 * a * x_n - x_n-l)

        n
(2a -1)
(1   0)

Note that Nth power of matrix could be found with log(N) matrix multiplications by means of exponentiation by squaring