如何评估以模数为模的指数塔

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)根据符合我们的条件欧拉定理:

  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)和简单的模幂运算.

如果a和m不是互质怎么办？这种情况并不像以前那么令人愉快,因为对所有人来说可能没有有效n的财产.然而,我们可以证明该序列的进入之后的某一时刻一个周期,也就是存在和使用,使得对所有.a^T mod m = a^(T mod n) mod mTa^k mod mk = 0, 1, 2, ...xCx, C < ma^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)每次递归的取幂的算法.

如果我们想做得更好怎么办？感谢Math Exchange的Jyrki Lahtonen提供以下算法的基本知识!

让我们评估的顺序d_k = gcd(a^k, m),直到我们找到一个x有d_x = d_{x+1}.这将最多采用log(m)GCD计算,因为x它受到素数因子分解中的最高指数的限制m.我们C = phi(m / d_x).现在,我们可以证明 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).