모듈러 지수화는 (알고리즘은 잘못된 대답을 제공합니다)

Question

내가 모듈러 지수화를 구현하려고하지만 난 정답을 얻을 수 없습니다

공공 정적 BigInteger를 modPow (이 BigInteger B, BigInteger의 전자,이 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 

Answer 1

의 객체를 반환합니다. 지수가 2 이고 지수가 2 인 경우 동일한 결과를 얻지 않습니까?

이러한 진술은 if 절 나와야하고, 비트는 0 또는 1인지 여부, 루프의 각 반복에서 실행될 : e.testBit(i)를 이용하여 지수 비트 반복, 또한

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

더 효율적이고 이해하기 쉬울 것입니다. 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; 
    } 

}