Question

C++ 怎么计算会溢出的大数乘方

加密算法中需要计算两个数的乘方，两个数会很大，肯定溢出（例如3的93次方）。 请问怎么处理这样的数据？ 不是RSA里的乘方再模除， 不模除，需要乘方结果参与后面的运算
就这么多分了，求大神指点。

Answer 1

如果你坚持要算这么大的数，那就先分配足够的空间，比如说3^93，就至少要17字节的内存，分段相乘，每次加上进位项，你可以参考以前4字节整形数据乘法的实现方式（以前是16位的寄存器，一次只能处理16位的数据，所以要分段处理）。不过还是建议你优化算法，尽量不算这么大的数。

追问

能绕开这种计算当然更好，我要计算 ((a^b×c^d)mod p)mod q
(a^b)mod p 可以计算 前面的a^b*c^d可以绕开吗？
还有麻烦分段相乘进位的方法能更详细一点吗？ 是用数组存储吗？ 谢谢~

追答

这个完全是可以避开的。
(a*b) % c = ((a%c) * (b%c)) % c，这个证明已经有人给出了，因此你只要将2个数的模相乘再取模
对于某个数的幂取模，如(a^b)%p可以证明其结果随b的变化是循环的。

证明如下：
对于a^b、a^(b+1)....a^(b+p)，其中必然存在2个数对P取模结果是相同的，因为对p取模结果只有p种，而有p+1个数。假设(a^(b+m))%p=(a^(b+m+n))%p，由(a*b) % c = ((a%c) * (b%c)) % c知，对任意整数d,(a^(b+m+d))%p=(a^(b+m+n+d))%p,进而引申至对任意整数e,(a^e)%p=(a^(e+n))%p,因此构成循环。
证明可能有点乱，这些东西现在都忘得差不多了。不过还有点印象，应该是类似于循环群的概念

Answer 2

若求(a * b) % c，
设 a % c = i, b % c = j， 则 a = m * c + i, b = n * c + j (m, n为整数)
推导可知：
a * b = (m * c + i) * (n * c + j) = (m*n*c + m*j + n*i) * c + i * j
则 (a * b) % c = (i * j) % c
总结就是： (a*b) % c = ((a%c) * (b%c)) % c

所以，只要把a^b×c^d适当分组，每组乘积分别取模后相乘，然后再取模。
结果是一样的，同时避免溢出。

Answer 3

你不模除肯定溢出啊，不模除要么保留进位部分，要么保留余数部分，肯定信息不完整了

追问

就是想知道怎么处理会溢出的数据 我现在需要完整的乘方结果继续运算。 我是想问怎么才能保留完整的结果