Модульное обратное и BigInteger деление

Question

Я работал над проблемой вычисления модульной инверсии большого целого числа, то есть a ^ -1 mod n. и использовал встроенную функцию BigInteger modInverse, чтобы проверить мою работу.

Я кодировал алгоритм, как показано в «Руководстве по прикладной криптографии» Menezes, et al. К сожалению для меня, я не получаю правильный результат для всех целых чисел.

Я думаю, что строка 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
б: 2 ^ 809 - 1

Пример ввода, который дает ожидаемые результаты:
а: 123456789
б: 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 имеют противоположные знаки.

Answer 2

Чтобы ваш код работал, вам нужно сохранить исходное значение модуля, которое вы можете создать в начале: BigInteger m = b; Затем, когда вы получите окончательный результат в x2, чтобы избежать отрицательных значений, которые могут возникнуть в результате Евклидова алгоритма, вычислите: x2.add (m), который будет мультипликативным обратным BigInteger a, mod (b), в соответствии с вашим код.

Answer 3

Измените return x2; на return y2;, и ваша программа даст правильный ответ.

Редактировать , этот ответ больше не действителен, поскольку верхний постер изменил свой код.