Java中的模块化幂运算 [英] Modular Exponentiation in Java
本文介绍了Java中的模块化幂运算的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我需要一种计算方法:
(g^u * y^v) mod p
在Java中.
我已经找到了用于计算(g ^ u)mod p的算法:
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.
将其放在上下文中是针对精简" DSA的Java实现-验证部分要求对此进行解决.
To put it in context, it's for a java implementation of a "reduced" DSA - the verifying part requires this to be solved.
推荐答案
假设这两个因素不会溢出,我相信您可以通过以下方式简化这样的表达式:
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
.我相信您可以从那里弄清楚.
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p
. I'm sure you can figure it out from there.
这篇关于Java中的模块化幂运算的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文