CODEWITHSUNDEEP
javamathbiginteger
axiomer
axiomer

Reputation: 2126

BigInteger modInverse not working with numbers checked to be invertible

I get this error message:

Exception in thread "main" java.lang.ArithmeticException: BigInteger not invertible.

This is strange because I've checked whether it's invertable like this but with a while:

if(e.gcd(f)==BigInteger.valueOf(1)){d=e.modInverse(f);}

(I use modInverse only once so the problem can be only this.) I also tried out using the equals function to checks, same result, and replacing BigInteger.valueOf(1) with BigInteger.ONE, also the same result.

e and f are both pretty big numbers. Can that be the problem? If not, what?

Edit: two numbers which should be good (e and f are both randomly generated): e: 9621052046061456501366587335847490032034738260531416442599992125724770869143777724434621136148270408224358486480789065076015439260049732834961669339663651068040517049948746219457579643120163445760970644691744741533662899190172821721584052976577686282851438621400884199179254302505283244747995592596611537181094200162016550417633813815524000523611778694711681246885146830340987509832366125391293211772272830763010707464147876271519220158561249284055201778976275 f:16676513155155711435633556290292399841994478533147079158165313450742666183857468374630705186073152798730185754009359158564262184760166850555421565829031677397531160732952407631566282672221888347405139275392725582249315145105384589417633027161798592285078352417743828277682057499510687432654973434263500652446355805121287249351524290685634309632867270787070026404872073959084720337580246072021126301925486445661096650037029829869513910200205317091132530162195304846449018937204755880662935929704531348715166585715335080615831412163500338513091079355521203276478413800219497108551811002174097217821125116752809771773184 .

Upvotes: 2

Views: 8504

Answers (1)

assylias
assylias

Reputation: 328598

Your numbers are not prime to each other:

public static void main(String... args) throws Exception {
    BigInteger e = new BigInteger("9621052046061456501366587335847490032034738260531416442599992125724770869143777724434621136148270408224358486480789065076015439260049732834961669339663651068040517049948746219457579643120163445760970644691744741533662899190172821721584052976577686282851438621400884199179254302505283244747995592596611537181094200162016550417633813815524000523611778694711681246885146830340987509832366125391293211772272830763010707464147876271519220158561249284055201778976275");
    BigInteger f =  new BigInteger("16676513155155711435633556290292399841994478533147079158165313450742666183857468374630705186073152798730185754009359158564262184760166850555421565829031677397531160732952407631566282672221888347405139275392725582249315145105384589417633027161798592285078352417743828277682057499510687432654973434263500652446355805121287249351524290685634309632867270787070026404872073959084720337580246072021126301925486445661096650037029829869513910200205317091132530162195304846449018937204755880662935929704531348715166585715335080615831412163500338513091079355521203276478413800219497108551811002174097217821125116752809771773184");
    System.out.println(e.gcd(f)); //prints 3
    BigInteger d;
    if (e.gcd(f).equals(BigInteger.ONE)) {
        d = e.modInverse(f);
        System.out.println(d);
    } else {
        System.out.println("nop");
    }
}

Now with the numbers below it works:

public static void main(String... args) throws Exception {
    BigInteger e = new BigInteger("2");
    e = e.pow(2048);
    BigInteger f =  e.add(BigInteger.ONE);
    System.out.println(e.gcd(f)); //1
    BigInteger d;
    if (e.gcd(f).equals(BigInteger.ONE)) {
        d = e.modInverse(f);
        System.out.println(d);
    } else {
        System.out.println("nop");
    }
}

Upvotes: 3

Related Questions