5

我需要一种计算方法：

(g^u * y^v) 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;
}

它工作得很好，但我似乎无法找到一种方法来做到这一点

(g^u * y^v) mod p

因为我的数学能力很差。

把它放在上下文中，它是用于“简化” DSA 的 java 实现 - 验证部分需要解决这个问题。

4

3 回答 3

9

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.

于 2010-11-01T06:45:51.717 回答
4

该代码片段实现了众所周知的“快速求幂”算法，也称为“平方求幂” 。

它还使用了 (a * b) mod p = ((a mod p) * (b mod p)) mod p 这一事实。（加法和乘法都是采用素数模数的保留结构——它是同态）。这样，在算法中的每一点，它都会减少到小于 p 的数字。

虽然您可以尝试在循环中以交错方式计算这些，但这样做并没有真正的好处。只需分别计算它们，将它们相乘，最后一次取模。

请注意，如果 p^2 大于最大的可表示 int，您将得到溢出，这将导致您得到错误的答案。对于 Java，切换到大整数可能是谨慎的，或者至少对 p 的大小进行运行时检查并抛出异常。

最后，如果这是出于加密目的，您可能应该使用库来执行此操作，而不是自己实现它。很容易做一些看似有效的轻微错误，但提供的安全性极低甚至没有。

于 2010-11-01T07:12:49.803 回答
1

尝试

(Math.pow(q, u) * Math.pow(y, v)) % p

于 2010-11-01T06:27:47.483 回答