Java 中的模幂运算
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4066952/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Modular Exponentiation in Java
提问by Carl Hagen
I need a way to calculate:
我需要一种计算方法：
(g^u * y^v) mod p
in Java.
在爪哇。
I've found this algorithm for calculating (g^u) mod p:
我找到了这个计算 (g^u) mod p 的算法：
int modulo(int a,int b,int c) {
long x=1
long y=a;
while(b > 0){
if(b%2 == 1){
x=(x*y)%c;
}
y = (y*y)%c; // squaring the base
b /= 2;
}
return (int) x%c;
}
and it works great, but I can't seem to find a way to do this for
而且效果很好，但我似乎找不到办法做到这一点
(g^u * y^v) mod p
as my math skills are lackluster.
因为我的数学能力很差。
To put it in context, it's for a java implementation of a "reduced" DSA - the verifying part requires this to be solved.
把它放在上下文中，它是一个“简化的”DSA 的 Java 实现——验证部分需要解决这个问题。
回答by Christian Mann
Assuming that the two factors will not overflow, I believe you can simplify an expression like that in this way:
假设这两个因素不会溢出，我相信你可以这样简化这样的表达式：
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p. I'm sure you can figure it out from there.
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p. 我相信你可以从那里弄清楚。
回答by wnoise
That fragment of code implements the well known "fast exponentiation" algorithm, also known as Exponentiation by squaring.
该代码片段实现了众所周知的“快速取幂”算法，也称为平方取幂。
It also uses the fact that (a * b) mod p = ((a mod p) * (b mod p)) mod p. (Both addition and multiplications are preserved structures under taking a prime modulus -- it is a homomorphism). This way at every point in the algorithm it reduces to numbers smaller than p.
它还使用了 (a * b) mod p = ((a mod p) * (b mod p)) mod p 的事实。（加法和乘法都是采用质数模数的保留结构——它是同态的）。这样，在算法中的每一点，它都会减少到小于 p 的数字。
While you could try to calculate these in an interleaved fashion in a loop, there's no real benefit to doing so. Just calculate them separately, multiply them together, and take the mod one last time.
虽然您可以尝试在循环中以交错方式计算这些，但这样做并没有真正的好处。只需分别计算它们，将它们相乘，最后一次取模数即可。
Be warned that you will get overflow if p^2 is greater than the largest representable int, and that this will cause you to have the wrong answer. For Java, switching to big integer might be prudent, or at least doing a runtime check on the size of p and throwing an exception.
请注意，如果 p^2 大于可表示的最大整数，则会出现溢出，这将导致您得到错误的答案。对于 Java，切换到大整数可能是谨慎的，或者至少对 p 的大小进行运行时检查并抛出异常。
Finally, if this is for cryptographic purposes, you should probably be using a library to do this, rather than implementing it yourself. It's very easy to do something slightly wrong that appears to work, but provides minimal to no security.
最后，如果这是出于加密目的，您可能应该使用库来执行此操作，而不是自己实现。很容易做一些看似可行的小错误，但提供的安全性极低甚至没有。
回答by Rogach
Try
尝试
(Math.pow(q, u) * Math.pow(y, v)) % p
(Math.pow(q, u) * Math.pow(y, v)) % p
