java - 在 Java 中更快地重新制定方程式

Question

我是做加密的，私钥指数d，需要d乘以e再取模，余数为1，函数i已经是这样了:

private void genD() {
        d = e / 2;
        // solve for d given d*e = 1 (mod eN)
        while ((d * e) % eN != 1) {
            d++;
        }
}

我现在所拥有的显然是一种粗暴的做事方式，遍历每个数字直到一个有效。我知道方程式起作用，使用找到的工作示例插入数字 here ，但是使用我生成的数字非常非常慢。从逻辑上讲，我觉得有一种方法可以更快地完成这项工作，但我想不出怎么做？

感谢任何帮助!提前致谢:)

Answer 1

有一些并不十分困难的快速乘法逆算法，但也有一种内置于 Java 中的算法:

 BigInteger.valueOf(e).modInverse(BigInteger.valueOf(eN)).intValue();

计算乘法逆模另一个数的最流行算法是 http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers .