我正在实现 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 的二进制形式。
感谢任何帮助。
最佳答案
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) 矩阵乘法找到
关于c# - 有效地计算卢卡斯序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23741966/