我要有效地计算^^ b模m为A，B，M＆LT较大值; 2 ^ 32 其中，^^的迭代幂次运算符：2 ^^ 4 = 2 ^（2 ^（2 ^ 2））

I have to compute efficiently a^^b mod m for large values of a,b,m<2^32 where ^^ is the tetration operator: 2^^4=2^(2^(2^2))

m不是质数，而不是10的功率。

m is not a prime number and not a power of ten.

你能帮忙吗？

推荐答案

需要明确的是，一个^^ b不是一回事作为^ B，它是指数塔^（一^（A ^ .. ^一）），其中有一个B复制，也被称为迭代幂次。设T（A，B）=一个^^ B以便T（A，1）= a和T（A，B）=一个^ T（A，B-1）。

To be clear, a^^b is not the same thing as a^b, it is the exponential tower a^(a^(a^...^a)) where there are b copies of a, also known as tetration. Let T(a,b) = a^^b so T(a,1) = a and T(a,b) = a^T(a,b-1).

要计算T（A，B）模m = A ^ T（A，B-1）模m，我们要计算的模m的功率有一个非常大的指数。有什么可以用的是模幂是在m的质因子分解，这是最log_2米的素数最的最大功率preperiodic用preperiod长度和周期长度分岛（M） ，其中phi（m）为欧拉函数。实际上，周期长度划分的米卡迈克尔的功能时，拉姆达（米）。因此，

To compute T(a,b) mod m = a^T(a,b-1) mod m, we want to compute a power of a mod m with an extremely large exponent. What you can use is that modular exponentiation is preperiodic with preperiod length at most the greatest power of a prime in the prime factorization of m, which is at most log_2 m, and the period length divides phi(m), where phi(m) is Euler's totient function. In fact, the period length divides Carmichael's function of m, lambda(m). So,

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

要小心，一个不一定互素米（或更高版本，披（M），岛（岛（M））等）。如果是这样，你可以说，一个^ķ模m = A ^（K MOD岛（M））模m。然而，这并不总是正确的，当a和m不互质。例如，披（100）= 40，2 ^ 1模100 = 2，但2 ^ 41 MOD 100 = 52，可以减少较大的指数，以全等数模披（M），其至少log_2男，所以你可以说，2 ^ 10001 MOD 100 = 2 ^ 41模100，但你不能减少到2 ^ 1模100。您可以定义一个模m [最小x]，也可以分+ MOD（一分钟，M）只要>最小

Be careful that a is not necessarily relatively prime to m (or later, to phi(m), phi(phi(m)), etc.). If it were, you could say that a^k mod m = a^(k mod phi(m)) mod m. However, this is not always true when a and m are not relatively prime. For example, phi(100) = 40, and 2^1 mod 100 = 2, but 2^41 mod 100 = 52. You can reduce large exponents to congruent numbers mod phi(m) that are at least log_2 m, so you can say that 2^10001 mod 100 = 2^41 mod 100 but you can't reduce that to 2^1 mod 100. You could define a mod m [minimum x] or use min + mod(a-min,m) as long as a>min.

如果T（A，B-1）> [log_2 M]，然后

If T(a,b-1) > [log_2 m], then

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

否则只是计算^ T（A，B-1）模m。

otherwise just calculate a^T(a,b-1) mod m.

递归地计算这一点。你可以用拉姆达（M）代替岛（M）。

Recursively calculate this. You can replace phi(m) with lambda(m).

它并不需要很长时间来计算下2 ^ 32的数字的质因子分解，因为你可以决定在2 ^ 16 = 65,536审判部门的主要因素。数论状披和lambda功能很容易EX pressed在因式分解方面。

It doesn't take very long to compute the prime factorization of a number under 2^32 since you can determine the prime factors in at most 2^16 = 65,536 trial divisions. Number-theoretic function like phi and lambda are easily expressed in terms of the prime factorization.

在每个步骤中，您将需要能够计算出与小指数模块化的权力。

At each step, you will need to be able to calculate modular powers with small exponents.

您最终计算的权力mod岛（M），然后启动mod岛（岛（M）），然后启动mod岛（岛（岛（M）））等，它并不需要很多迭代前迭代披功能1，​​这意味着你减少一切为0，而你不再得到任何改变，通过增加塔的高度。

You end up calculating powers mod phi(m), then powers mod phi(phi(m)), then powers mod phi(phi(phi(m))), etc. It doesn't take that many iterations before the iterated phi function is 1, which means you reduce everything to 0, and you no longer get any change by increasing the height of the tower.

下面是包含在高中数学竞赛，参赛者都应该重新认识这一点，并用手工执行它的类型的例子。什么是14 ^^ 2016的最后两位数字？

Here is an example, of a type that is included in high school math competitions where the competitors are supposed to rediscover this and execute it by hand. What are the last two digits of 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。

So, 14^14^14^...^14 ends in the digits ...36.