Implement modInverse using Extended Euclid Algorithm in Java

Question

modInverse method of class BigInteger should not be used. I tried and used this method but it does not produce the correct result. Any help would be appreciated.

public static int[] extendedgcd(int a, int b) {
        if (b==0) {
            return new int[]{1, 0, a};
        } else {
            int output[] = extendedgcd(b, a%b);
            return new int[]{output[0], output[0]-((a/b)*output[1]), output[2]};
        }
    }

Zecong Hu · Accepted Answer · 2021-05-22 17:12:10Z

1

In the else-branch, the first return value should be output[1] instead of output[0]:

public static int[] extendedgcd(int a, int b) {
    if (b == 0) {
        return new int[]{1, 0, a};
    } else {
        int output[] = extendedgcd(b, a % b);
        return new int[]{
            output[1],
            output[0] - ((a / b) * output[1]),
            output[2]
        };
    }
}

You can test the implementation here: https://onlinegdb.com/volwDTwnl

answered May 22, 2021 at 17:12

Zecong Hu

3,4821 gold badge22 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

SomeDude Over a year ago

Since OP seems to want to implement modInverse , its worth mentioning that if the gcd given by output[2] is 1 then output[0] is the inverse of a modulus b, otherwise there doesn't exist such inverse i.e. a, b are not coprime.

Collectives™ on Stack Overflow

Implement modInverse using Extended Euclid Algorithm in Java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related