我需要一種方法來計算：模冪在Java中
(g^u * y^v) mod p
。
我發現這個算法計算（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實現 - 驗證部分要求解決這個問題。
假設這兩個因素不會溢出，我相信你可以這樣簡化表達式：
(x * y) mod p = ((x mod p)*(y mod p)) mod p。我相信你可以從那裏弄清楚。
是的，我認爲這是方式，到目前爲止，我已經完成了對這個小數字的測試，並且它似乎正在工作 – 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
這段代碼實現了衆所周知的「快速求冪」算法，也稱爲Exponentiation by squaring。它也使用（a * b）mod p =（（a mod p）*（b mod p））mod p的事實。 （加法和乘法都是保持結構在取一個模數 - 它是一個同態）。這種方式在算法的每一點都會減少到小於p的數字。
儘管您可以嘗試以循環方式計算這些值，但這樣做並沒有真正的好處。只需分別計算它們，將它們相乘，然後最後一次使用mod。
請注意，如果p^2大於最大的可表示整數，則會發生溢出，並且這會導致您錯誤的答案。對於Java，切換到大整數可能是謹慎的，或者至少在運行時檢查p的大小並拋出異常。最後，如果這是爲了加密的目的，你應該使用一個庫來做到這一點，而不是自己實現它。做一些稍微錯誤的工作似乎很容易，但提供的安全性最低。
這確實是用於加密目的，但它是我們自己實施DSA的學校作業。謝謝你有見地的答案！ – 2010-11-01 07:19:40
我假設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