c# - 有效地计算卢卡斯序列

Question

我正在实现 p+1 分解算法。为此，我需要计算由以下定义的卢卡斯序列的元素:

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

我递归地实现了它 (C#)，但它对于更大的索引来说效率低下。

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;
    }

我也知道

(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) 和 (4) 应该有助于计算更大的 Q。但我不确定如何。我想以某种方式使用 Q 的二进制形式。

感谢任何帮助。

Answer 1

Here可以看到如何使用矩阵乘方找到第 N 个斐波那契数

      n
(1 1)
(1 0)

您可以利用这种方法来计算卢卡斯数，使用矩阵(对于您的情况 x_n+l = 2 * a * x_n - x_n-l)

        n
(2a -1)
(1   0)

请注意，矩阵的 N 次方可以通过 exponentiation by squaring 的 log(N) 矩阵乘法找到