我正在实现 p+1 分解算法。为此,我需要计算 lucas 序列的元素,该序列由以下定义:
我用递归实现了它(使用C#),但对于较大的索引来说效率不高。
我也知道。
Lucas(n) = 0 if n=0, Lucas(1) = 1, Lucas(n) = P*Lucas(n-1) - Q*Lucas(n-2)
(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的二进制形式来实现。
非常感谢您的帮助。
N
的事实可能会很有用。对于N
的值是否有其他限制吗? - Samuel Edwin Ward