Java中的高效BigInteger乘法模数

Question

我可以计算两个BigIntegers(比如a和b)模数n的乘法.

这可以通过以下方式完成:

a.multiply(b).mod(n);

但是,假设a和b具有相同的n阶,则意味着在计算过程中,正在计算新的BigInteger,并且其长度(以字节为单位)为~ 2n.

我想知道我是否可以使用更高效的实现.像modMultiply这样的东西像modPow一样实现(我相信它不会计算功率,然后是模数).

Answer 1

您可以使用通用数学，例如： (A*B) mod N = ((A mod N) * (B mod N)) mod N

它可能更需要 CPU 密集型，但应该在 CPU 和内存之间进行选择，对吗？

如果我们谈论模运算，那么蒙哥马利简化可能正是您所需要的。但不知道任何开箱即用的解决方案。