模冪（算法給出了錯誤的答案）

Question

我想實現模冪，但我不能得到正確的答案：

公共靜態的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 

Answer 1

的對象你不這樣做的零指數位什麼。你會不會得到2 指數和2 指數相同的結果？

這些陳述應該出來的if子句的，並且在循環的每個迭代被執行，則該位是否爲0或1：

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

而且，迭代使用e.testBit(i)指數的位會更有效率，更易於理解。即使使用modPow()不允許，testBit()應該沒問題。

---

這是我的版本，包括修復bug和我的建議，以擺脫字符串轉換。它似乎也適用於一般數字。它不處理負指數和一些其他特殊情況。

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; 
    } 

}