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

我正在加密,对于私钥指数d,你需要将d乘以e并取另一个数的mod,并将余数设为1.我已经具有的函数是：privatevoidgenD(){de2;solvefordgivend*e

我正在加密,对于私钥指数d,你需要将d乘以e并取另一个数的mod,并将余数设为1.我已经具有的函数是：

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

我现在所拥有的显然是一种蛮横的做事方式,经历每一个数字直到一个有效.我知道方程式完成它的工作,使用找到的工作示例插入数字here,但是使用我正在生成的数字非常非常慢.从逻辑上讲,我觉得有一种方法可以更快地完成这项任务,但我无法想到如何做到这一点？

任何帮助表示赞赏！提前致谢 ：)

解决方法:

有快速乘法逆算法并不是非常困难,但也有一个内置于Java：

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

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