Modular Inverse and BigInteger division
- by dano82
I've been working on the problem of calculating the modular inverse of an large integer i.e. a^-1 mod n. and have been using BigInteger's built in function modInverse to check my work.
I've coded the algorithm as shown in The Handbook of Applied Cryptography by Menezes, et al. Unfortunately for me, I do not get the correct outcome for all integers.
My thinking is that the line q = a.divide(b) is my problem as the divide function is not well documented (IMO)(my code suffers similarly). Does BigInteger.divide(val) round or truncate? My assumption is truncation since the docs say that it mimics int's behavior. Any other insights are appreciated.
This is the code that I have been working with:
private static BigInteger modInverse(BigInteger a, BigInteger b) throws ArithmeticException {
//make sure a >= b
if (a.compareTo(b) < 0) {
BigInteger temp = a;
a = b;
b = temp;
}
//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;
}
