Модульное возведение в степень в java (алгоритм дает неверный ответ)

Я пытаюсь реализовать модульное возведение в степень, но не могу получить правильный ответ:

общедоступный статический 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

java exponentiation modular
person user2835815    schedule 13.03.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы ничего не делаете для нулевых битов экспоненты. Разве вы не получите одинаковые результаты для показателя степени 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;
  }

}
person erickson    schedule 13.03.2014
comment
Это может быть мой любимый комментарий StackOverflow. - person erickson; 14.03.2014
comment
Я ПРОБОВАЛ НОМЕР С 512-БИТ, И ЭТО НЕ РАБОТАЕТ :( - person user2835815; 14.03.2014
comment
@user2835815 user2835815 Я тестировал его с множеством разных 512-битных показателей, и все они работали. Какие параметры пробовали? Каков был результат? - person erickson; 14.03.2014
comment
я использовал случайный класс для генерации чисел (вероятное простое число) - person user2835815; 14.03.2014
comment
он дает число, но оно неверно в соответствии с modpow в классе BigInteger, если вы сравните его. - person user2835815; 14.03.2014
comment
@user2835815 user2835815 Что ж, если вы правильно применили исправление, оно должно работать. Вам нужно будет предоставить определенный набор параметров для тестирования, если вы считаете, что он все еще не работает. Я выложил свой код для сравнения. - person erickson; 14.03.2014