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方法。