Geek Answers Handbook

Modular Inverse and BigInteger Unit

I worked on the problem of computing a modular inverse large integer, i.e. a ^ -1 mod n. and used BigInteger built-in to the modInverse function to test my work.

I encoded the algorithm as shown in the Applied Cryptography Guide from Menezes, et al. Unfortunately for me, I am not getting the correct result for all integers.

My thinking is that the q = a.divide (b) line is my problem as the split function is not well documented (IMO) (my code suffers the same way). Does BigInteger.divide (val) make round or truncated? My guess is truncation, as the docs say it mimics int behavior. Any other ideas appreciated.

This is the code I worked with:

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

+5
3

return x2; return y2;, .

, , .

0

Java:

JLS 15.17.2

0. , , n d, , q, |d·q|<=|n|; , q , |n|>=|d| n d , q , |n|>=|d| n d .

+5

, , : BigInteger m = b; , x2, , , : x2.add(m), BigInteger a, mod (b), .

0

More articles:


All Articles