数学研发论坛

 找回密码
 欢迎注册
查看: 499|回复: 7

[提问] 求a^a^……^a mod p的余数

[复制链接]
发表于 2018-8-21 16:11:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
试设计一个算法,可以计算$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$,程序里要考虑到这种费马小定理不能直接使用的情况。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-21 18:42:52 | 显示全部楼层
通过测试,发现个规律,当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,...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-22 00:50:27 | 显示全部楼层
可以先求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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-22 07:35:39 来自手机 | 显示全部楼层
不论p是多少,是否素数,对于充分大的k,余数必然是常数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-22 08:44:17 | 显示全部楼层
对于给定的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)$必然是常数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-22 09:02:26 | 显示全部楼层
比如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)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-8-23 12:26:10 | 显示全部楼层
\[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}}}}}}}}}}}}}}}}}}}}}}}}}}\]
这个题目的意义是?纯粹为了计算而计算?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-8-23 12:56:38 | 显示全部楼层
本帖最后由 lsr314 于 2018-8-23 12:58 编辑
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的既约剩余系。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-2-17 18:12 , Processed in 0.050454 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表