计算一个数字的模数（该功率的数量非常大）
我想自己计算RSA算法。 我需要计算一定功率下的数的模数。 问题在于那个特定能量的数字会变得很大。
这就是我想要的：
x = pow(n, p) % q 我怎样才能有效地确定x？
如果您使用的是.NET 4，我建议您查看BigInteger ，它甚至提供了ModPow方法，只需一次操作即可完成所有操作:)
BigInteger n = ...; BigInteger p = ...; BigInteger q = ...; BigInteger x = BigInteger.ModPow(n, p, q);
这被称为powermodfunction ：
function modular_pow(base, exponent, modulus) c := 1 for e_prime = 1 to exponent c := (c * base) mod modulus return c
通过平方应用求幂可以提高效率：
function modular_pow(base, exponent, modulus) result := 1 while exponent > 0 if (exponent & 1) equals 1: result = (result * base) mod modulus exponent := exponent >> 1 base = (base * base) mod modulus return result
请查看本主题和本文，了解如何使数学函数本身更有效。
请参阅BigInteger.ModPow （Fx 4+），这是MSDN 。
平凡……
x = 1 for(i = 0; i < p; i++) x = (x*n) % q
更有效的方法，如二进制求幂而不是这种天真的迭代，但这确实超过了溢出问题，因为x受n * q的限制
虽然这里提供的所有答案都是正确的，但我错误地使用了明显的平方和乘法算法，这是实现模幂运算的“经典”方法。
如果您打算编写自己的Modpow()版本：
您只需要模幂q，因此您的计算不需要使用大于q^2任何数字，使用以下事实：
if a = b (mod q) then a*p = b*p (mod q)
因此，在计算功率n^p ，在每次乘法后，对工作变量执行（模q）运算。
另外，如果q是素数，你可以使用费马的小定理，其中指出：
a^(q-1) = 1 (mod q) (when a is not a multiple of q)
当p （大于）大于q时，这可用于缩短计算