algorithm - 如何计算 a^^b mod m？

Question

对于较大的 a,b,m<2^32
，我必须有效地计算 a^^b mod m其中 ^^ 是四元运算符:2^^4=2^(2^(2^2))

m 不是质数，也不是 10 的幂。

你能帮忙吗？

Answer 1

要明确的是，a^^b 和 a^b 不是一回事，它是指数塔 a^(a^(a^...^a)) 其中有 b 个 a 的副本，也称为滴定。令 T(a,b) = a^^b 所以 T(a,1) = a 和 T(a,b) = a^T(a,b-1)。

为了计算 T(a,b) mod m = a^T(a,b-1) mod m，我们想要计算具有极大指数的 mod m 的幂。可以使用的是模幂是前周期的，前周期长度至多为m的质因数分解中素数的最大幂，最多为log_2 m，周期长度除以phi(m)，其中phi(m)是Euler's totient function .事实上，周期长度除以 Carmichael's function的 m，lambda(m)。所以，

a^k mod m = a^(k+phi(m)) mod m as long as k>log_2 m.

请注意，a 不一定与 m(或稍后与 phi(m)、phi(phi(m)) 等)互质。如果是，你可以说 a^k mod m = a^(k mod phi(m)) mod m。然而，当 a 和 m 不互质时，情况并非总是如此。例如，phi(100) = 40，2^1 mod 100 = 2，但是 2^41 mod 100 = 52。您可以将大指数减少为至少为 log_2 m 的同余数 mod phi(m)，因此您可以说 2^10001 mod 100 = 2^41 mod 100 但你不能将其减少到 2^1 mod 100。你可以定义一个 mod m [minimum x] 或使用 min + mod(a-min,m)只要 a>min.

如果 T(a,b-1) > [log_2 m]，则

a^T(a,b-1) mod m = a^(T(a,b-1) mod phi(m) [minimum [log_2 m]])

否则只需计算 a^T(a,b-1) mod m。

递归计算。您可以将 phi(m) 替换为 lambda(m)。

计算 2^32 以下数字的质因数分解不需要很长时间，因为您最多可以在 2^16 = 65,536 次试验中确定质因数。 phi 和 lambda 等数论函数很容易用质因数分解表示。

在每一步中，您都需要能够计算具有小指数的模幂。

你最终会计算 powers mod phi(m)，然后 powers mod phi(phi(m))，然后 powers mod phi(phi(phi(m)))，等等。之前不需要那么多迭代迭代的 phi 函数为 1，这意味着您将所有内容都减少为 0，并且不再通过增加塔的高度来获得任何变化。

这是一个示例，属于高中数学竞赛中包含的一种类型，参赛者应该重新发现并手工执行。 14^^2016 的最后两位数是多少？

14^^2016 mod 100 
= 14^T(14,2015) mod 100
= 14^(T(14,2015) mod lambda(100) [minimum 6]) mod 100
= 14^(T(14,2015 mod 20 [minimum 6]) mod 100

T(14,2015) mod 20 
= 14^T(14,2014) mod 20
= 14^(T(14,2014) mod 4 [minimum 4]) mod 20

T(14,2014) mod 4
= 14^T(14,2013) mod 4
= 14^(T(14,2013 mod 2 [minimum 2]) mod 4

T(14,2013) mod 2
= 14^T(14,2012) mod 2
= 14^(T(14,2012 mod 1 [minimum 1]) mod 2
= 14^(1) mod 2
= 14 mod 2
= 0

T(14,2014) mod 4 
= 14^(0 mod 2 [minimum 2]) mod 4
= 14^2 mod 4
= 0

T(14,2015) mod 20
= 14^(0 mod 4 [minimum 4]) mod 20 
= 14^4 mod 20
= 16

T(14,2016) mod 100
= 14^(16 mod 20 [minimum 6]) mod 100
= 14^16 mod 100
= 36

因此，14^14^14^...^14 以数字 ...36 结尾。