Implement modInverse (bigint version does not support even modulus yet).

tests/corelib/big_integer_arith_vm_test.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Testing Bigints with and without intrinsics.
 // VMOptions=
 // VMOptions=--no_intrinsify
 
 library big_integer_test;
 import "package:expect/expect.dart";
@@ skipping 205 matching lines @@
   x = 123456789012345678901234567891;
   e = 123456789012345678901234567899;
   m = 123456789012345678901234567890;
   Expect.equals(1, x.modPow(e, m));
   x = 123456789012345678901234567891;
   e = 123456789012345678901234567890;
   m = 123456789012345678901234567899;
   Expect.equals(40128068573873018143207285483, x.modPow(e, m));
 }
 
+testBigintModInverse() {
+  var x, m;
+  x = 1234567890;
+  m = 19;
+  Expect.equals(11, x.modInverse(m));
+  x = 1234567890;
+  m = 1000000001;
+  Expect.equals(189108911, x.modInverse(m));
+  x = 19;
+  m = 1000000001;
+  Expect.equals(0, x.modInverse(m));  // Not coprime.
+  x = 19;
+  m = 1234567890;
+  Expect.equals(519818059, x.modInverse(m));
+  x = 1000000001;
+  m = 1234567890;
+  Expect.equals(1001100101, x.modInverse(m));
+  x = 1000000001;
+  m = 19;
+  Expect.equals(0, x.modInverse(m));  // Not coprime.
+  x = 12345678901234567890;
+  m = 19;
+  Expect.equals(3, x.modInverse(m));
+  x = 12345678901234567890;
+  m = 10000000000000000001;
+  Expect.equals(9736746307686209582, x.modInverse(m));
+  x = 19;
+  m = 10000000000000000001;
+  Expect.equals(6315789473684210527, x.modInverse(m));
+  x = 19;
+  m = 12345678901234567890;
+  Expect.equals(0, x.modInverse(m));  // TODO(regis): Even modulus.
+  x = 10000000000000000001;
+  m = 12345678901234567890;
+  Expect.equals(0, x.modInverse(m));  // TODO(regis): Even modulus.
+  x = 10000000000000000001;
+  m = 19;
+  Expect.equals(7, x.modInverse(m));
+  x = 12345678901234567890;
+  m = 10000000000000000001;
+  Expect.equals(9736746307686209582, x.modInverse(m));
+  x = 12345678901234567890;
+  m = 19;
+  Expect.equals(3, x.modInverse(m));
+  x = 123456789012345678901234567890;
+  m = 123456789012345678901234567899;
+  Expect.equals(0, x.modInverse(m));  // Not coprime.
+  x = 123456789012345678901234567890;
+  m = 123456789012345678901234567891;
+  Expect.equals(123456789012345678901234567890, x.modInverse(m));
+  x = 123456789012345678901234567899;
+  m = 123456789012345678901234567891;
+  Expect.equals(77160493132716049313271604932, x.modInverse(m));
+  x = 123456789012345678901234567899;
+  m = 123456789012345678901234567890;
+  Expect.equals(0, x.modInverse(m));  // TODO(regis): Even modulus.
+  x = 123456789012345678901234567891;
+  m = 123456789012345678901234567890;
+  Expect.equals(0, x.modInverse(m));  // TODO(regis): Even modulus.
+  x = 123456789012345678901234567891;
+  m = 123456789012345678901234567899;
+  Expect.equals(46296295879629629587962962962, x.modInverse(m));
+}
+
 testBigintNegate() {
   var a = 0xF000000000000000F;
   var b = ~a;  // negate.
   Expect.equals(-0xF0000000000000010, b);
   Expect.equals(0, a & b);
   Expect.equals(-1, a | b);
 }
 
 testShiftAmount() {
   Expect.equals(0, 12 >> 111111111111111111111111111111);
@@ skipping 11 matching lines @@
   Expect.equals(1234567890123456789, foo());
   Expect.equals(12345678901234567890, bar());
   testSmiOverflow();
   testBigintAdd();
   testBigintSub();
   testBigintMul();
   testBigintTruncDiv();
   testBigintDiv();
   testBigintModulo();
   testBigintModPow();
+  testBigintModInverse();
   testBigintNegate();
   testShiftAmount();
   Expect.equals(12345678901234567890, (12345678901234567890).abs());
   Expect.equals(12345678901234567890, (-12345678901234567890).abs());
   var a = 10000000000000000000;
   var b = 10000000000000000001;
   Expect.equals(false, a.hashCode == b.hashCode);
   Expect.equals(true, a.hashCode == (b - 1).hashCode);
 }