Java 中的模幂
我需要一种计算方法：
(g^u * y^v) mod p
用Java。
我发现了这个计算 (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;
}
它效果很好，但我似乎找不到一种方法来做到这一点，
(g^u * y^v) mod p
因为我的数学技能很差。
放在上下文中，它是“简化”DSA 的 java 实现 - 验证部分需要解决这个问题。
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:
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
假设这两个因子不会溢出，我相信您可以这样简化表达式：
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p(x * y) mod p = ( (x mod p)*(y mod p) ) mod p.我相信你可以从那里弄清楚。
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.该代码片段实现了众所周知的“快速求幂”算法，也称为平方求幂。
它还使用 (a * b) mod p = ((a mod p) * (b mod p)) mod p 的事实。 （加法和乘法都是在取素数模的情况下保留的结构——它是同态）。这样，算法中的每个点都会减少到小于 p 的数字。
虽然您可以尝试在循环中以交错方式计算这些值，但这样做并没有真正的好处。只需分别计算它们，将它们相乘，最后一次取模即可。
请注意，如果 p^2 大于可表示的最大 int，您将发生溢出，这将导致您得到错误的答案。对于 Java，切换到大整数可能是谨慎的做法，或者至少对 p 的大小进行运行时检查并抛出异常。
最后，如果这是出于加密目的，您可能应该使用库来执行此操作，而不是自己实现。很容易做一些看似有效的轻微错误，但提供的安全性极低甚至没有。
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.
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.
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.
尝试
Try
下面是一些示例代码，它输入原始问题中的变量并遵循 Christian Mann 的答案。
BigInteger 解决了溢出问题。
返回语句是一个 BigInteger。
Here's some sample code that inputs the variables in the original question and follows on from Christian Mann's answer.
BigInteger gets around the overflow issues.
The return statement is a BigInteger.