BigInteger到BigInteger的功能（Schnorr簽名）

Question

我想在Java中實現Schnorr簽名算法。我面臨用大指數（例如MD5哈希數）計算功率的問題。

有什麼辦法讓BigInteger獲得BigInteger的權力嗎？

我需要計算（a^x * b^y）％z其中y是非常大的數字。有沒有計算這種表達式的方法？

由於

Answer 1

我終於找到了解決方案。

(a * b) % p = ((a % p) * (b % p)) % p 

所以我的例子是這樣的：我可以非常快使用這種技術計算我的表達

(a^x * b^y) % z = (((a^x) % z) * ((b^y) % z)) % z; 

，或者使用的BigInteger在Java中：

BigInteger result = a.modPow(x, z).multiply(b.modPow(y, z)).mod(z); 

Answer 2

號的最大值的BigInteger支持是2 ^{Integer.MAX_VALUE的} -1。這個澄清的句子已被添加到Java 8中的BigInteger javadoc，但實施過程在相當長一段時間內一直存在。

的BigInteger必須支持範圍爲-2 ^{Integer.MAX_VALUE的}（不包括）值以2 ^{Integer.MAX_VALUE的}（不包括），並且可以支持該範圍以外的值。

正如其他人指出的，您可能需要使用modPow而不是計算中間值。

作爲對比，宇宙中估計有10⁸⁰（或2 ）個原子。

Answer 3

對於Schnorr簽名算法，您實際上需要組合的功率和模數運算。由於涉及的數字潛在巨大，因此僅僅進行權力運作是沒有意義的。

您需要使用BigInteger class的modPow方法。