python - 查找涉及指数的余数模和涉及大数的除法

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 次方和模 ((a-1)*p) 相加。这可以使用 Python pow() 函数来完成。然后调整为 -1 并除以 a-1。

使用 pow() 函数并传递模值比计算完整指数然后取模更快，因为模可以在计算的每个阶段应用于部分乘积，这阻止了值得到太大(10⁶ 的 10⁶ 次方有 600 万个十进制数字，在每一步应用模数时，值永远不必增长到大于模 - 在这个例子中大约 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)

输出:

444446

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