如何计算^^ b mod m？

Question

对于a，b，m的大数值，我必须有效地计算a ^^ b mod m，其中^^是tetration运算符：2 ^^ 4 = 2 ^（2 ^（2^2 ））

m不是质数而不是十的幂。

你能帮忙吗？

Answer 1

要清楚，a ^^ b与a^b不是一回事，它是指数塔a ^（a ^（a^...^a）），其中有b个副本，也被称为tetration。假设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_2m，周期长度除phi（m），其中phi（m）是Euler's totient function。实际上，周期长度除以m，lambda（m）的Carmichael's function。所以，

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

要小心，一个不一定相对素M（或更高版本，披（M），披（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 m（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米]，然后

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

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

递归地计算这个。你可以用lambda（m）替换phi（m）。

因为您可以在至多2^16 = 65,536试验分区中确定素数因子，所以计算2^32以下数字的素数因子分解不需要很长时间。像phi和lambda这样的数论函数很容易用素因子分解来表示。

在每一步中，您都需要能够计算具有小指数的模块化功率。你最终计算功率mod phi（m），然后为mod phi（phi（m））赋权，然后给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。