Java中的模幂运算

Question

我需要一种计算的方法：

(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实现 - 验证部分需要解决这个问题。

- Carl Hagen

---

是的，p是质数，我认为这可以解决它：(g^u * y^v) mod p = (g^u mod p) * (y^v mod p) mod p。虽然到目前为止我只用小数进行了测试。 - Carl Hagen

而且它很大吗？对我来说，“mod p”部分似乎就像是如果你想使用BigInteger而不是长整型。 - Roland Illig

是的，p很大（在我的情况下，具体为23929） - Carl Hagen

Answer 1

假设两个因子不会溢出，我相信你可以通过以下方式简化这样的表达式：
(x * y) mod p = ( (x mod p)*(y mod p) ) mod p。我相信你可以从中理解。

- Christian Mann

---

是的，我认为这是正确的方法，到目前为止我已经对小数字进行了测试，看起来它是有效的。 - Carl Hagen

我猜想假设这些因素不会溢出可能是不可行的，但我不能确定。 - Michael McGowan

只要(p-1)*(p-1)适合于'int'，因子就不会溢出。否则，我们将不得不使用'long'来表示x和y。 - MAK

Answer 2

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

它还利用了(a * b) mod p = ((a mod p) * (b mod p)) mod p这个事实。(在取质数模下，加法和乘法都是保留结构——这是一个同态映射)。这样，在算法的每个点上，它都会缩小到小于p的数字。

虽然你可以尝试在循环中交错地计算它们，但这样做没有真正的好处。只需将它们分别计算，相乘，最后再取模即可。

请注意，如果p^2大于最大表示int，则会溢出，并导致你得到错误的答案。对于Java来说，切换到大整数可能是明智的选择，或者至少对p的大小进行运行时检查并抛出异常。

最后，如果这是用于加密目的，你应该使用库来完成这个任务，而不是自己实现。很容易做一些微不足道的错误，看起来工作正常，但提供极少或根本没有安全性。

- wnoise

---

这确实是用于加密目的，但它是为了我们学校的作业而实现DSA。感谢您深入的回答！ - Carl Hagen

Answer 3

尝试

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

- Rogach

---

我猜他问的原因是数字太大了，简单的方法行不通... - Michael McGowan

如果是这种情况，为什么不使用BigInteger呢？ - Nicholas

Math.pow()接受和返回double类型。http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Math.html#pow%28double,%20double%29 - wnoise

Answer 4

这里有一些示例代码，输入了原始问题中的变量，并继续使用了Christian Mann的答案。 BigInteger避免了溢出问题。 返回语句是一个BigInteger。

    public static BigInteger ModularExponent(BigInteger G, BigInteger U, BigInteger Y, BigInteger V, BigInteger P) {
      
      return ((G.modPow(U,P)).multiply(Y.modPow(V,P))).mod(P);
    }

- Anthony Overmars