java - 模逆和 BigInteger 除法

Question

我一直在研究计算大整数的模逆的问题，即 a^-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 = r;
        x2 = x1;
        x1 = x;
        y2 = y1;
        y1 = y;
    }
    if (!a.equals(BigInteger.ONE))
        throw new ArithmeticException("a and n are not coprime");
    return x2;
}

产生错误输入的输入示例是:
一个:123456789
b: 2^809 - 1

产生预期结果的输入示例是:
一个:123456789
b: 2^807 - 1

Answer 1

以下是 Java 语言规范中整数除法的规定:

JLS 15.17.2 Division Operator

Integer division rounds toward 0. That is, the quotient produced for operands n and d that are integers after binary numeric promotion is an integer value q whose magnitude is as large as possible while satisfying |d·q|<=|n|; moreover, q is positive when |n|>=|d| and n and d have the same sign, but q is negative when |n|>=|d| and n and d have opposite signs.