回复 26楼 Crocodile_JX
那天说的是不太清楚，我又整理了一下思路。
可不可以把 “计算出满足 a ~ c^d(mod n) 的 a”理解成求 (c^d)%n 的值？
我当时就是这么理解的，因为和 c^d 关于模 n 同余的数非常多，但是介于 0 ~ n-1 之内的就只有一个，这个数就是 (c^d)%n 。
现在说怎么求 (c^d)%n。直接求 c^d 肯定会溢出，所以得换种求法。
假设已知 [c^(d-1)]%n = f，问能不能利用 f 求 (c^d)%n？方法如下：
因为 [c^(d-1)]%n = f，就是说 c^(d-1) 除以 n 的余数是 f。假设商是 k，那么根据带余除法：
c^(d-1) = kn + f。
于是：
c^d = c * c^(d-1) = ckn + cf。
现在要求 (c^d)%n，ckn 必是 n 的倍数。所以 c^d 与 cf 同余。
即 (c^d) % n = cf % n。
现在就可以往回推了，想求 [c^(d-1)]%n 就要求 [c^(d-2)]%n，……
最后是 c % n，这就是 f 的初始值。
其实就是说，在求 c^d 次方时，不是一直乘，而是每次乘完都取一次模，就可以在不溢出的情况下求出 c^d%n。这么解释是不是清楚一点？
所以我感觉代码写成下面这样可能可读性更好一点，它更像是表示每次乘完后取模：
程序代码：
f = 1;
while (--d) {
f = f * c % n;
}
不过严格来看，还有几个值得商榷的问题。咱们这么算是为了避免计算 c^d 时溢出，但这么算会不会溢出呢？
做除法肯定没问题，主要是关心乘法。c*f 会不会溢出(就是超过 2^32)？
这里 f 是介于 0 ~ n-1 之间的一个数。可以认为它相对较小，但当 c 很大时，它还是有可能溢出。不过由于 c, f 都是小于32次方的，所以它们的积不会超过64次方。如果 e 用 long long 表示的话，就不用担心溢出了。
另一种想法是，可不可以先减小 c 的值，比如先把 c = c % n 一下？
我感觉可能是可以的。咱先记 c' = c % n，从而 c = ln + c'。
c^d = c*c^(d-1) = c(kn+f) ~ cf = (ln+c')f = lnf + c'f ~ c'f
只看最左一项和最右一项，就是 c^d ～ c'f，所以应该也是可以的。
这样一来 c'*f 肯定是小于 n^2 的，所以如果 n < 2^16 次方，就肯定不会溢出，而不用使用 long long 类型。
呵呵，不过上面说的都是凭空想的，包括给的那个代码也没试过。你可以写几个函数，用用不同的算法，看看实际算出来是不是一样的。理论的主说到底只是一种指导思想而已。
而且这个算法应该还能改进，比如如果知道了 c^2 是不是可以直接去算 c^4，而跳过求 c^3 这步？
我举个例子，c^7 ＝ c^(4+2+1) = c^4 * c^2 * c。
由于同余是一种线性运算，即如果关于模 m，有： a ~ b, c ~ d 则 ac ~ bd。
（证明：由已知: m|(a-b), m|(c-d)。由于：ac-bd = ac-bc+bc-bd = c(a-b)+b(c-d)。从而 m|(ac-bd)，即 ac~bd。）
所以事实上只要求出 2的幂次方 的各个同余的結果，最終的結果只要把它们再乘起来就够了。
如果这个方法可行，c^1024 次方，就只用算大约10余次乘法就够了，而不是一千多次。
同样是理论指导一下，具体是否可行，自己还得再推一推。不过要用到的数学技巧应该都在这了。
你的数学很好，厉害。