求余数 mod 涉及指数和涉及大数的除法

Question

我需要一个快速算法来评估以下内容

((a^n-1)/(a-1)) % p

a 和 n 几乎相等但小于 10^6，并且 p 是固定素数（假设 p=1000003）。我需要在 1 秒内计算出来。我正在使用 python。 Wolfram Mathematica computes it instantly。使用以下代码需要 35.2170000076 秒

print (((10**6)**(10**6)-1)/((10**6)-1))%1000003

如果分母 a-1 不存在，我可以将幂分成更小的顺序并使用关系 a*b (mod c) = (a (mod c) * b (mod c)) (mod c) 但分母存在。

如何用快速算法来评估这个？没有 numpy/scipy 可用。

UPDATE:: 这是我想出的最终代码

def exp_div_mod(a, n, p):
    r = pow(a, n, p*(a-1)) - 1
    r = r - 1 if r == -1 else r
    return r/(a-1)

Answer 1

(((a ** n) - 1) / (a-1)) % p

可以改写为

(((a ** n) - 1) % ((a-1)*p)) / (a-1)

这部分：

(((a ** n) - 1) % ((a-1)*p))

可以这样计算：

((a ** n) % ((a-1)*p))

然后调整为 -1。

a 的 n 次方，mod((a-1)*p)。这可以使用 Python pow() 函数来完成。然后调整为 -1 并除以 a-1。

使用 pow() 函数并传递一个 modulo 值比计算完整指数然后取 modulo 更快，因为可以应用 modulo到计算的每个阶段的部分乘积，这会阻止值变得太大（10⁶ 的 10⁶ 次方有 6百万十进制数字，在每一步应用 modulo，值永远不必增长到大于 modulo 的大小——在这个例子中大约 13 位）。

代码：

def exp_div_mod(a, n, p):
    m = p * (a - 1)
    return ((pow(a, n, m) - 1) % m) // (a - 1);

print exp_div_mod((10**6), (10**6), 1000003)

输出：

注意：此方法仅在 a、n 和 p 为整数时有效。

Answer 2

您可以乘以 p - 1 的 modular inverse。由于费马小定理，你有 x^p-2 · x ≡ x^p-1 ≡ 1 (mod p) 对于所有 0 < x < p，所以你甚至不需要扩展欧几里得来计算逆，只需要 pow 函数标准 Python:

(pow(a, n, p) - 1) * pow(a - 1, p - 2, p) % p

算法时间复杂度(log p)因为使用了square-and-multiply

Answer 3

(aⁿ−1) ⁄ (a−1) 是 i = 0 到 n−1 的 a 的总和ⁱ.

计算后者 mod p 很简单，基于以下内容：

设F(a,n)为Σ( i=0..n-1){aⁱ} 如果 n > 0，否则为 0.

现在：

F(a,n) = a×F(a,n−1) + 1
F(a,2n) = (a+1)×F(a²,n )

第二个身份是分而治之递归。

由于这两个都只涉及加法和乘法，我们可以计算它们 mod p 而不需要大于 a[= 的整数类型75=]×p通过分配modulus运算。（见下面的代码。）

只需第一次递归，我们就可以编写迭代解决方案：

def sum_of_powers(a, n, p): sum = 0 for i in range(n): sum = (a * sum + 1) % p return sum

同样使用分而治之的递归，我们得到的结果并不复杂：

def sum_of_powers(a, n, p): if n % 2 == 1: return (a * sum_of_powers(a, n-1, p) + 1) % p elif n > 0: return ((a + 1) * sum_of_powers(a * a % p, n // 2, p)) % p else: return 0

第一个解决方案 returns 在不到一秒的时间内 n == 10⁶。第二个returns瞬间，即使n大到10⁹.

求余数 mod 涉及指数和涉及大数的除法

Finding remainder mod involving exponent and division involving huge numbers

python

language-agnostic

algorithm

math