java - java中的模幂(算法给出了错误的答案)

标签 java modular exponentiation

我正在尝试实现模幂,但我无法得到正确的答案:

public static BigInteger modPow(BigInteger b, BigInteger e, BigInteger m)

{//计算模幂并返回BigInteger类的对象

    BigInteger x= new BigInteger("1"); //The default value of x

    BigInteger power ;

    power=b.mod(m);

    String  t =e.toString(2); //convert the power to string of binary

    String reverse = new StringBuffer(t).reverse().toString();




    for (int i=0;i<reverse.length();i++ )  { //this loop to go over the string char by char by reverse

        if(reverse.charAt(i)=='1') { //the start of if statement when the char is 1
          x=x.multiply(power);
          x=x.mod(m);
          power=power.multiply(power);
          power=power.mod(m);

        } //the end of if statement



        }//the end of for loop


        return x;

    } //the end of the method modPow

最佳答案

对于零指数位,您无需执行任何操作。对于指数 20 和指数 22048 不会得到相同的结果吗?

这些语句应该来自 if 子句,并在循环的每次迭代中执行,无论该位是零还是一:

power=power.multiply(power);
power=power.mod(m);

此外,使用 e.testBit(i) 迭代指数位会更高效且更容易理解。即使不允许使用 modPow()testBit() 也应该没问题。

<小时/>

这是我的版本,包括错误的修复以及我摆脱字符串转换的建议。对于一般数字来说,它似乎也可以可靠地工作。它不处理负指数和其他一些特殊情况。

public class CrazyModPow
{

  public static void main(String[] argv)
  {
    for (int count = 1; true; ++count) {
      Random rnd = new Random();
      BigInteger base = BigInteger.probablePrime(512, rnd);
      BigInteger exp = BigInteger.probablePrime(512, rnd);
      BigInteger mod = BigInteger.probablePrime(1024, rnd);
      if (!base.modPow(exp, mod).equals(modPow(base, exp, mod))) {
        System.out.println("base: " + base);
        System.out.println("exp:  " + exp);
        System.out.println("mod:  " + mod);
      }
      else if ((count % 10) == 0) {
        System.out.printf("Tested %d times.%n", count);
      }
    }
  }

  public static BigInteger modPow(BigInteger base, BigInteger e, BigInteger m)
  {
    BigInteger result = BigInteger.ONE;
    base = base.mod(m);
    for (int idx = 0; idx < e.bitLength(); ++idx) {
      if (e.testBit(idx)) {
        result = result.multiply(base).mod(m);
      }
      base = base.multiply(base).mod(m);
    }
    return result;
  }

}

关于java - java中的模幂(算法给出了错误的答案),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22392541/

相关文章:

java - 如何使用显示方法和调用构造函数?

Java 8 Stream——聚合和返回聚合步骤

c - 实现基于整数的幂函数 pow(int, int) 的最有效方法

java - 如何使用 JDBC 更新 MySQL-PreparedStatement 中未知数量的列?

java - 如何向模块路径添加依赖项?

c++ - 模块化 C++ 设计

python - scipy.sparse 矩阵的逐元素幂

javascript - 简单地将数字的平方相加

haskell - Haskell 中的模算术

Codeigniter 模块化扩展