模块化逆和BigInteger划分

Question

我一直在研究计算大整数的模逆的问题,即^ -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;
}

输出错误输入的示例是:
a:123456789
b:2 ^ 809 - 1

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

Answer 1

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

JLS 15.17.2分部操作员

整数除法向0舍入.也就是说,为操作数生成的商n和d二进制数字提升后的整数是一个整数值,q其大小尽可能大,同时满足|d·q|<=|n|; 而且,q当|n|>=|d|和,n并且d具有相同的符号时是正的,但是q当|n|>=|d|和n并且d具有相反的符号时是否定的.