模冪在Java中

我需要一種方法來計算：模冪在Java中

(g^u * y^v) mod p

在Java中

。

我發現這個算法計算（G^U）模p：

int modulo(int a,int b,int c) { 
    long x=1 
    long y=a; 
    while(b > 0){ 
     if(b%2 == 1){ 
      x=(x*y)%c; 
     } 
     y = (y*y)%c; // squaring the base 
     b /= 2; 
    } 
    return (int) x%c; 
}

和它的偉大工程，但我似乎無法找到一種方法，爲

(g^u * y^v) mod p

做到這一點

因爲我的數學技能是平淡無奇。

把它放在上下文中，它是針對一個「減少」DSA的java實現 - 驗證部分要求解決這個問題。

來源

2010-11-01 Carl Hagen

我假設p是素數，對不對？ – 2010-11-01 06:35:59

是的，p是素數，我認爲這解決了它：（g^u * y^v）mod p =（g^u mod p）*（y^v mod p）mod p，儘管我只用到目前爲止的小數字 – 2010-11-01 06:45:58

它是大嗎？如果你想使用'BigInteger'而不是長時間，'mod p'部分就像我一樣。 – 2010-11-01 06:47:51

假設這兩個因素不會溢出，我相信你可以這樣簡化表達式：

(x * y) mod p = ((x mod p)*(y mod p)) mod p。我相信你可以從那裏弄清楚。

來源

2010-11-01 06:45:51

是的，我認爲這是方式，到目前爲止，我已經完成了對這個小數字的測試，並且它似乎正在工作 – 2010-11-01 06:52:45

我猜測這可能不行假設這些因素不會溢出，但我無法確定。 – 2010-11-01 06:53:02

只要（p-1）*（p-1）適合在int內，因素就不會溢出。否則，我們只需要對x和y使用'long's。事實 – MAK 2010-11-01 07:17:02

嘗試

（Math.pow（Q，U）* Math.pow（Y，V））％P

來源

2010-11-01 06:27:47 Rogach

我猜他是問的原因是，數字太大，工作簡單的方法... – 2010-11-01 06:31:28

如果是這樣的話，爲什麼不使用BigInteger？ – Nicholas 2010-11-01 06:52:14

Math.pow（）接受並返回雙打。 http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Math。html＃pow％28double，％20double％29 – wnoise 2010-11-01 07:21:21

這段代碼實現了衆所周知的「快速求冪」算法，也稱爲Exponentiation by squaring。它也使用（a * b）mod p =（（a mod p）*（b mod p））mod p的事實。（加法和乘法都是保持結構在取一個模數 - 它是一個同態）。這種方式在算法的每一點都會減少到小於p的數字。

儘管您可以嘗試以循環方式計算這些值，但這樣做並沒有真正的好處。只需分別計算它們，將它們相乘，然後最後一次使用mod。

請注意，如果p^2大於最大的可表示整數，則會發生溢出，並且這會導致您錯誤的答案。對於Java，切換到大整數可能是謹慎的，或者至少在運行時檢查p的大小並拋出異常。最後，如果這是爲了加密的目的，你應該使用一個庫來做到這一點，而不是自己實現它。做一些稍微錯誤的工作似乎很容易，但提供的安全性最低。

來源

2010-11-01 07:12:49 wnoise

這確實是用於加密目的，但它是我們自己實施DSA的學校作業。謝謝你有見地的答案！ – 2010-11-01 07:19:40

模冪在Java中

回答

相關問題