algorithm - 如何评估以质数为模的指数塔

Question

我想找到一种快速算法来评估如下表达式，其中 P 是素数。

A ^ B ^ C ^ D ^ E mod P

例子:

(9 ^ (3 ^ (15 ^ (3 ^ 15)))) mod 65537 = 16134

问题是中间结果会变得太大而无法处理。

Answer 1

基本上，问题归结为计算 a^T mod m对于给定 a , m和一个术语 T那是大得离谱。但是，我们能够评估 T mod n具有给定的模数 n比 T 快得多.所以我们问:“是否有一个整数 n ，使得 a^(T mod n) mod m = a^T mod m ？”

现在如果a和 m是互质的，我们知道 n = phi(m)根据 Euler's theorem 满足我们的条件:

  a^T                               (mod m)
= a^((T mod phi(m)) + k * phi(m))   (mod m)    (for some k)
= a^(T mod phi(m)) * a^(k * phi(m)) (mod m)
= a^(T mod phi(m)) * (a^phi(m))^k   (mod m)
= a^(T mod phi(m)) * 1^k            (mod m)
= a^(T mod phi(m))                  (mod m)

如果我们可以计算phi(m) (例如在 O(m^(1/2)) 中很容易做到，或者如果我们知道 m 的质因数分解)，我们已将问题简化为计算 T mod phi(m)和一个简单的 modular exponentiation .

如果 a 会怎样和 m不是互质的吗？情况不像以前那么愉快，因为可能没有有效的 n。与属性(property) a^T mod m = a^(T mod n) mod m对于所有 T .但是，我们可以证明序列 a^k mod m对于 k = 0, 1, 2, ...在某个点后进入一个循环，即存在x和 C与 x, C < m , 这样 a^y = a^(y + C)对于所有 y >= x .

示例:对于 a = 2, m = 12 ，我们得到序列 2^0, 2^1, ... = 1, 2, 4, 8, 4, 8, ... (mod 12) .我们可以看到带参数的循环 x = 2和 C = 2 .

我们可以通过计算序列元素 a^0, a^1, ... 来通过蛮力找到循环长度直到我们找到两个索引 X < Y与 a^X = a^Y .现在我们设置 x = X和 C = Y - X .这给了我们一个算法 O(m)每次递归求幂。

如果我们想做得更好怎么办？感谢Jyrki Lahtonen来自 Math Exchange 提供 the essentials for the following algorithm !

让我们评估序列d_k = gcd(a^k, m)直到我们找到 x与 d_x = d_{x+1} .这最多需要 log(m) GCD 计算，因为 x以 m 的质因数分解中的最高指数为界.让C = phi(m / d_x) . We can now prove that a^{k + C} = a^k对于所有 k >= x , 所以我们在 O(m^(1/2)) 中找到了循环参数时间。

假设我们找到了x和 C并想计算 a^T mod m现在。如果T < x ，使用简单的模幂执行任务是微不足道的。否则，我们有 T >= x因此可以利用循环:

  a^T                                     (mod m)
= a^(x + ((T - x) mod C))                 (mod m)
= a^(x + (-x mod C) + (T mod C) + k*C)    (mod m)     (for some k)
= a^(x + (-x mod C) + k*C) * a^(T mod C)  (mod m)
= a^(x + (-x mod C)) * a^(T mod C)        (mod m)

同样，我们已将问题简化为相同形式的子问题(“计算 T mod C”)和两个简单​​的模幂运算。

由于模数在每次迭代中至少减少 1，我们得到一个相当弱的边界 O(P^(1/2) * min (P, n))对于该算法的运行时间，其中 n是栈的高度。在实践中，我们应该做得更好，因为模量预计会呈指数下降。当然这个论点有点曲折，也许一些更喜欢数学的人可以改进它。

有一些边缘情况需要考虑，它们实际上可以让您的生活更轻松一些:如果m = 1，您可以立即停止。 (在这种情况下结果为 0)或者如果 a是 m 的倍数(在这种情况下结果也是 0)。

编辑:可以证明x = C = phi(m)是有效的，因此我们可以使用公式作为一种快速而肮脏的解决方案

a^T = a^(phi(m) + T mod phi(m))  (mod m)

T >= phi(m)甚至 T >= log_2(m) .