Java BigInteger，數論，模塊化算術

Question

任何人都有關於如何在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; 
} 

Answer 1

心慌這個被擱置了...

對於理論的緣故，如果您想編寫自己的自定義方法，請根據數學技巧檢查以下內容，以避免計算。首先是解決方案，然後是數學背後的數學。

你的子程序可能類似於以下內容：

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

現在的解釋

爲了解釋事情，我做的數字更小......這是手工過程，get變成了代碼e結束。

• 讓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

或二進制

這可以通過編程從0迭代到我們的BigInteger b的.bitLength()和與.testBit()給定的位檢查被發現。 因此，Java代碼中的for循環。

下一頁我們發現您的基本模數的倍數（n）目標（你需要去爲遠在價值作爲您的兩個最高功率從之前的段）：

暫且稱之爲每一個簡化值爲a<power_of_2>。

• 一個模N = A1
• 一個^ 2模N = A2
• 一個^ 4模N =（A2）^ 2模N = A4模N
• 一個^ 8模N = （A4）^ 2模N = A8模N
• ...

和手工值：

• 17^％5 =
• 17^％5 = 2^2模5 = 4模5 =
• 17^％5 = 4^2模5 = 16模5 =
• 17^％5 = 1^2模5 = 1模5 =
• 17^％5 = 1^2模5 = 1模5 =
• 17^％5 = 1^2模5 = 1模5 =

問題在於這可以與先前找到base2權力的步驟同步完成，每次迭代也可以找到最新的a<power_of_2>。每個額外的平方需要計算，直到我們達到最大值，因此循環中的值不斷增加previous。

最後，我們把我們的neccessary一個值和多個它們交相輝映，其次是我們的n模量。 這是在foor-loop的if語句中。

• 再次，我們有權力： + + + + +

和從我們具有上述步驟取這些值並將它們放在一起（，後面跟着循環末尾的模數）：

* * * * * ％5 = 8％5 = 3

Answer 2

可以使用BigInteger類這一點，如果你是不是迫切需要的性能。 BigInteger是不可變的。

public static BigInteger getValue(int a, int b, int n) { 
    return BigInteger.valueOf(a).modPow(BigInteger.valueOf(b), BigInteger.valueOf(n)); 
} 

Answer 3

要回答你的問題直接， 我想BigInteger.modPow可能是你在找什麼。

public BigInteger modPow(BigInteger exponent, 
        BigInteger m) 

返回一個BigInteger，其值是（這^指數模m）

可選擇地（並且更有效），也可以採取（國防部n）輸出到（B模N）的功率，這應該使代碼運行得更快。

（A^B模N）=（（國防部N）^（B模N）MOD N）