求a^a^……^a mod p的余数

lsr314

试设计一个算法，可以计算$f(a,k,p)=a^(a^(…^a)) mod p$的余数（等号右边有$k$个$a$）.
作为测试，应当可以得到以下结果$f(4,4,13)=4^(4^(4^4))=9(mod 13)$.
注意，以上例子可以划归为求$4^(4^4) mod 12$,但是$4$和$12$有共同的素因子$2$，程序里要考虑到这种费马小定理不能直接使用的情况。

kastin

通过测试，发现个规律，当k不断增大时，余数为模p简化剩余系中一些元素构成的循环系列

比如f(4,k,13)=4,9,12,1循环，f(5,k,13)=5循环，f(8,k,13)=1循环，等等。可见这个循环长度跟余数中现了a模p的乘法阶数(或其倍数)的次序有关。如果能确定循环长度，可以递归计算出这个循环序列即可。剩余就是直接对k求模循环长度的余数即可。

如果这个p为奇素数幂，则还可能出现的是收敛到一个固定余数的序列，比如f(3,k,169)=3,27,66,66,66,66,...，或者最终收敛到一个循环圈f(8,k,169)=8,79,161,151,122,77,21,47,122,77,21,47,...

kastin

可以先求a模p的乘法阶数，因为p为奇素数(2是平凡情形，不考虑)，故它必定是p-1的大于1的因子，对这些因子作a的模幂运算，从小到大可搜索到乘法阶数m；
对a按1到m次幂进行模p运算，然后对结果进行模m运算(若是m的倍数，余数规定为m而不是0)，得到一个长度为m的序列S；
然后从第一个开始,b=S(1)进行不断索引b=S(b)，直到第一次为b=1为止，依次记录这些结果，假设是长度为n的序列s。

那么f(a,k,p)=s(k mod n)

mathe

不论p是多少，是否素数，对于充分大的k,余数必然是常数

mathe

对于给定的a和n,形式$a^x(mod n)$必然最多除了开始若干项以后是关于变量x的周期序列，而且周期小于n(除了n=1)
我们可以记这个周期为$L_a(n)$,于是我们直到对于任意$n>1,1<=L_a(n)<n$
所以$a^(a^x) (mod n)$关于x的周期必然为$L_a^{(2)}(n)=L_a(L_a(n))$
同样$a^(a^{a^x})(mod n)$关于x的周期必然为$L_a^{(3)}(n)=L_a(L_a^{(2)}(n))$
由于序列$L_a^{(h)}(n)$严格递减，必然存在某个t使得$L_a^{(t)}(n)=1$
也就是对于$t>=h$以后，除了最多前面有限项$a^{a^{...^a}}(mod n)$必然是常数

mathe

比如kastin的f(8,k,169),显然f(8,1,169)=8,f(8,2,169)=79
由于$\varphi(169)=12*13=3*4*13$,所以$f(8,3,169)=8^f(8,2,3*4*13) (mod 169) -=8^40 (mod 169) -=53$
同样由于$a^x(mod 4)$周期为2,$a^x(mod 3)$周期为2,$a^x(mod 13)$周期为12
所以$8^{8^{8^x}} (mod 169)$的周期为$[2,2,12]=12$
$8^{8^{8^{8^x}}} (mod 169)$的周期最多为2，而$8^{8^{8^{8^{8^x}}}}(mod 169)$的周期必然为1，当然前面会有若干不符合周期的项

具体计算如下
由于$8^x(mod 2) -=0$,周期为1
而由于$\varphi(3) -=2$,所以$8^{8^x} (mod 3) -=8^0 (mod 3) -=1(mod 3)$周期为1
而由于$8^{8^x}(mod 4) -=0(mod 4)$,所以我们得出$8^{8^x} -=4(mod 12)$周期为1
所以$8^{8^{8^x}} (mod 3) -=8^4(mod 3) -=1(mod 3)$
$8^{8^{8^x}}(mod 4) -=0 (mod 4)$
$8^{8^{8^x}}(mod 13) -= 8^4 (mod 13) -=1(mod 13)$
所以得出$8^{8^{8^x}} -= 40 (mod 12*13)$
所以我们得出$8^{8^{8^{8^x}}} -= 8^40 (mod 169) -=53(mod 169)$
也就是$t>=4$时必然都有f(8,t,169)=53,也就是其对应序列其实是8,79,53,53,53,...

而$t=3$时就可以取到周期而不是$t=4$才取到是因为
$8^x (mod 12)$的周期为2，分别取值$8,4,8,4,...$
所以$8^(8^x) (mod 12) -=4 (mod 13)$, 而$8^(8^x) (mod 13)$在x为奇数等于$8^8(mod 13)$,周期x为偶数时等于$8^4(mod 13)$而两者这时都正好等于1，于是$8^(8^x) -= 40 (mod 3*4*13)$,所以$ 8^(8^{8^x}) (mod 169) -= 8^40 (mod 169)-=53 (mod 169)$

mathematica

\[8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8}}}}}}}}}}}}}}}}}}}}}}}}}}\]
这个题目的意义是?纯粹为了计算而计算?

lsr314

mathematica 发表于 2018-8-23 12:26
\[8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8^{8}}}}}}}}}}}}}}}}}}} ...

最开始是想看看有哪些a和p，满足f(a,k,p)经过所有p的既约剩余系。