如何以素数为模数评估指数塔 [英] How to evalute an exponential tower modulo a prime

问题描述

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

A ^ B ^ C ^ D ^ E mod P

示例:

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

问题在于中间结果可能变得太大而无法处理.

解决方案

从根本上讲，该问题减少了为给定的a，m和一个非常大的术语T计算a^T mod m.但是，我们能够以给定的模量n评估T mod n，其速度比T快得多.所以我们问:是否有整数n，例如a^(T mod n) mod m = a^T mod m?"

现在，如果a和m是互质的，我们知道n = phi(m)符合模幂.

如果a和m不是互质的怎么办?这种情况并不像以前那样令人愉快，因为对于所有T，可能都没有具有属性a^T mod m = a^(T mod n) mod m的有效n.但是，我们可以证明k = 0, 1, 2, ...的序列a^k mod m在某个点之后进入一个循环，即存在x和C与x, C < m，从而对于所有y >= x来说都是a^y = a^(y + C). /p>

示例:对于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 提供了我们现在可以针对所有k >= x证明 a^{k + C} = a^k，因此我们在时间.

假设我们已经找到了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).

I want to find a fast algorithm to evaluate an expression like the following, where P is prime.

A ^ B ^ C ^ D ^ E mod P

Example:

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

The problem is the intermediate results can grow much too large to handle.

解决方案

Basically the problem reduces to computing a^T mod m for given a, m and a term T that is ridiulously huge. However, we are able to evaluate T mod n with a given modulus n much faster than T . So we ask: "Is there an integer n, such that a^(T mod n) mod m = a^T mod m?"

Now if a and m are coprime, we know that n = phi(m) fulfills our condition according to 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)

If we can compute phi(m) (which is easy to do for example in O(m^(1/2)) or if we know the prime factorization of m), we have reduced the problem to computing T mod phi(m) and a simple modular exponentiation.

What if a and m are not coprime? The situation is not as pleasant as before, since there might not be a valid n with the property a^T mod m = a^(T mod n) mod m for all T. However, we can show that the sequence a^k mod m for k = 0, 1, 2, ... enters a cycle after some point, that is there exist x and C with x, C < m, such that a^y = a^(y + C) for all y >= x.

Example: For a = 2, m = 12, we get the sequence 2^0, 2^1, ... = 1, 2, 4, 8, 4, 8, ... (mod 12). We can see the cycle with parameters x = 2 and C = 2.

We can find the cycle length via brute-force, by computing the sequence elements a^0, a^1, ... until we find two indices X < Y with a^X = a^Y. Now we set x = X and C = Y - X. This gives us an algorithm with O(m) exponentiations per recursion.

What if we want to do better? Thanks to Jyrki Lahtonen from Math Exchange for providing the essentials for the following algorithm!

Let's evaluate the sequence d_k = gcd(a^k, m) until we find an x with d_x = d_{x+1}. This will take at most log(m) GCD computations, because x is bounded by the highest exponent in the prime factorization of m. Let C = phi(m / d_x). We can now prove that a^{k + C} = a^k for all k >= x, so we have found the cycle parameters in O(m^(1/2)) time.

Let's assume we have found x and C and want to compute a^T mod m now. If T < x, the task is trivial to perform with simple modular exponentiation. Otherwise, we have T >= x and can thus make use of the cycle:

  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)

Again, we have reduced the problem to a subproblem of the same form ("compute T mod C") and two simple modular exponentiations.

Since the modulus is reduced by at least 1 in every iteration, we get a pretty weak bound of O(P^(1/2) * min (P, n)) for the runtime of this algorithm, where n is the height of the stack. In practice we should get a lot better, since the moduli are expected to decrease exponentially. Of course this argument is a bit hand-wavy, maybe some more mathematically-inclined person can improve on it.

There are a few edge cases to consider that actually make your life a bit easier: you can stop immediately if m = 1 (the result is 0 in this case) or if a is a multiple of m (the result is 0 as well in this case).

EDIT: It can be shown that x = C = phi(m) is valid, so as a quick and dirty solution we can use the formula

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

for T >= phi(m) or even T >= log_2(m).

这篇关于如何以素数为模数评估指数塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！