我正在尝试计算一些正整数 a,b,c,p 的 a^b^c mod p。一种可能的（也是显而易见的）方法是使用快速模幂，它将运行在O(log(b^c))=clog(b)。虽然我不介意这里的效率，但这种方法的明显缺点是您需要一个显式的二进制表示b^c这本身就已经是指数级的了。
所以对我来说问题是如果我不能代表b^c作为二进制表示，有没有办法可以计算a^b^cmod p 来自二进制表示a,b, and c?
(a^b^c) mod p = (((a^b) mod p)^c) mod p
所以你可以做
modpow(modpow(a,b,p),c,p);
其中所有操作数结果和子结果都是普通整数。作为modpow您可以通过求模平方来使用幂p像这儿：
请注意，这些是利用特定选定的属性进行了一些优化p所以你需要改变线路
if (DWORD(d)>=DWORD(p)) d-=p;
into
d%=p;
[例子]
(2^3^5) % 6 =
(8 ^5) % 6 =
32768 % 6 = 2
(((2^3)%6)^5) % 6 =
(( 8 %6)^5) % 6 =
( 2 ^5) % 6 =
32 % 6 = 2
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
