小编Dan*_*lin的帖子

我一直在研究计算大整数的模逆的问题,即^ -1 mod n.并一直使用BigInteger的内置函数modInverse来检查我的工作.

我编写了算法,如Menezes等人的"应用密码学手册"所示.对我来说不幸的是,我没有得到所有整数的正确结果.

我的想法是线q = a.divide(b)是我的问题,因为除法函数没有很好地记录(IMO)(我的代码也遭受类似的影响).BigInteger.divide(val)是圆形还是截断？我的假设是截断,因为文档说它模仿int的行为.任何其他见解表示赞赏.

这是我一直在使用的代码:

private static BigInteger modInverse(BigInteger a, BigInteger b) throws ArithmeticException {
    //trivial case: b = 0 => a^-1 = 1
    if (b.equals(BigInteger.ZERO)) {
        return BigInteger.ONE;
    }
    //all other cases
    BigInteger x2 = BigInteger.ONE;
    BigInteger x1 = BigInteger.ZERO;
    BigInteger y2 = BigInteger.ZERO;
    BigInteger y1 = BigInteger.ONE;
    BigInteger x, y, q, r;
    while (b.compareTo(BigInteger.ZERO) == 1) {
        q = a.divide(b);
        r = a.subtract(q.multiply(b));
        x = x2.subtract(q.multiply(x1));
        y = y2.subtract(q.multiply(y1));
        a = b;
        b = …