-4

任何人都知道如何在 java 中实现这样的问题？

“实现一个子程序，它采用三个正整数参数 (a;b;n) 并返回 ((a 的 b 次幂) mod n) 的值，其中参数由大约 100 个十进制数字表示。使用四种不同的方法。”

提前致谢

UPD：方法如下

M1)

public BigInteger Result1(BigInteger a , BigInteger b , BigInteger n){
    BigInteger Res = new BigInteger("1");
    for (BigInteger i = new BigInteger("0"); !i.equals(b); i = i.add(new BigInteger("1"))) {
        Res = Res.multiply(a).mod(n);
    }
    return Res;
}

M2)

public BigInteger Result2(BigInteger a , BigInteger b , BigInteger n){
    BigInteger Res = new BigInteger("1");
    for (BigInteger i = new BigInteger("0"); !i.equals(b); i = i.add(new BigInteger("1"))) {
        Res = Res.multiply(a);
    }
    return Res.mod(n);
}

M3)

ublic BigInteger Result3(BigInteger a , BigInteger b , BigInteger n){
    if(b.equals(new BigInteger("0"))){
        return new BigInteger("1");
    }
    else if(b.mod(new BigInteger("2")).equals(new BigInteger("0"))){
        BigInteger Res = Result3(a,b.divide(new BigInteger("2")),n);
        return (Res.multiply(Res)).mod(n);
    }
    else{
        return ( (a.mod(n)).multiply(Result3(a, b.subtract(new BigInteger("1")), n)) ).mod(n);
    }
}

M4)

public BigInteger Result4(BigInteger a , BigInteger b , BigInteger n){
    BigInteger Res = new BigInteger("1");
    while(!b.equals(new BigInteger("0"))) {
        if(!(b.mod(new BigInteger("2"))).equals(new BigInteger("0"))) {
            Res = Res.multiply(a).mod(n);
        }
        a = a.multiply(a).mod(n);
        b = b.divide(new BigInteger("2"));
    }
    return Res;
}
4

3 回答 3

1

要直接回答您的问题，我认为BigInteger.modPow可能是您正在寻找的。

public BigInteger modPow(BigInteger exponent,
                     BigInteger m)

返回值为 (this^exponent mod m) 的 BigInteger

或者（并且更有效），您也可以将 (a mod n) 提高到 (b mod n) 幂，这应该会使代码运行得更快。

(a^b mod n) = ((a mod n)^(b mod n) mod n)

于 2014-12-19T01:35:24.133 回答
0

如果您不迫切需要性能，则可以使用BigInteger该类。BigInteger是不可变的。

public static BigInteger getValue(int a, int b, int n) {
    return BigInteger.valueOf(a).modPow(BigInteger.valueOf(b), BigInteger.valueOf(n));
}
于 2014-12-19T01:33:17.597 回答
0

惊慌失措，这被搁置了...

为了理论起见，如果您想编写自己的自定义方法，请根据数学技巧检查以下内容以避免计算。首先是解决方案，然后是其背后的数学。

您的子例程可能如下所示：

public static BigInteger customPowMod(BigInteger a, BigInteger b, BigInteger n){
    BigInteger previous = a.mod(n);
    BigInteger runningTotal = new BigInteger("1");
    for(int i = 0; i < a.bitLength(); i++){
        if(a.testBit(i)){
            runningTotal = runningTotal.multiply(previous);
        }
        previous = previous.multiply(previous).mod(n);
    }
    return runningTotal.mod(n);
}

以下是如何调用该方法的示例：

public static void main(String[] args) {
    BigInteger a = new BigInteger("1700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005");
    BigInteger b = new BigInteger("6300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005");
    BigInteger n = new BigInteger("50000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
    //note the following produce the same values
    System.out.println(customPowMod(a,b,n)); 
    System.out.println(a.modPow(b,n));
}

现在解释

为了解释事情，我正在做较小的数字......这是手工过程最终变成了代码。

  • 让a= 17
  • 让b= 63
  • 让n= 5

首先，您想查看您的功率数由什么 base2 功率b组成。例如：

63 = 2^5 + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 32 + 16 + 8 + 4 + 2 + 1。

或二进制11111

这可以通过从 0 迭代到我们的 BigInteger b .bitLength()并检查.testBit()给定位来以编程方式找到。因此，Java 代码中的 for 循环。

接下来，我们找到您的基本模数 ( ) 目标的倍数n（您的值需要与前一段中的 2 的最高幂一样远）：

让我们称每个简化值a<power_of_2>。

  • 模数 n = a1
  • a^2 模 n = a2
  • a^4 mod n = (a2)^2 mod n = a4 mod n
  • a^8 mod n = (a4)^2 mod n = a8 mod n
  • ...

和手工值：

  • 17^ 1 % 5 = 2
  • 17^ 2 % 5 = 2^2 模 5 = 4 模 5 = 4
  • 17^ 4 % 5 = 4^2 模 5 = 16 模 5 = 1
  • 17^ 8 % 5 = 1^2 模 5 = 1 模 5 = 1
  • 17^ 16 % 5 = 1^2 模 5 = 1 模 5 = 1
  • 17^ 32 % 5 = 1^2 模 5 = 1 模 5 = 1

有问题的是，这可以与查找 base2 幂的上一步同步完成，每次迭代您还可以找到最新的a<power_of_2>. 每个额外的平方都需要计算，直到我们达到最大值，因此previous循环中的值不断增加。

最后，我们取必要的 a 值并将它们相乘，然后是我们的模数n。这是在 for 循环的 if 语句中。

  • 同样，我们有权力：32 + 16 + 8 + 4 + 2 + 1

从上面的步骤中，我们获取了值并将它们组合在一起（然后是循环末尾的模数）：

1 * 1 * 1 * 1 * 4 * 2 % 5 = 8 % 5 = 3

于 2014-12-19T03:17:43.630 回答