如何计算^^ b mod m？

Question

我必须为a,b,m <2 ^ 32的大值有效地计算^^ b mod m,
其中^^是tetration运算符:2 ^^ 4 = 2 ^(2 ^(2 ^ 2))

m不是素数而不是10的幂.

你能帮我吗？

Answer 1

要清楚,^^ b与^ 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的幂.你可以使用的是模幂运算是预周期的,前期长度最多是素数因子分解中的素数的最大幂,最多为log_2 m,周期长度除以phi(m),其中phi(m)是欧拉的全部功能.实际上,周期长度除以卡迈克尔的函数 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 [最小x]或使用min + mod(a-min,m)只要一分钟.

如果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]])

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

递归计算这个.您可以用lambda(m)替换phi(m).

计算2 ^ 32以下数的素数因子化并不需要很长时间,因为您可以确定最多2 ^ 16 = 65,536个试验区的素数因子.像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.