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

tests/corelib/big_integer_arith_vm_test.dart

Index: tests/corelib/big_integer_arith_vm_test.dart
diff --git a/tests/corelib/big_integer_arith_vm_test.dart b/tests/corelib/big_integer_arith_vm_test.dart
index 4c04c03de1971c9f870f5100f662d837a7e809cc..a2d8ad23fd89675868e65ed398190c0f75323c62 100644
--- a/tests/corelib/big_integer_arith_vm_test.dart
+++ b/tests/corelib/big_integer_arith_vm_test.dart
@@ -223,6 +223,80 @@ testBigintModPow() {
   Expect.equals(40128068573873018143207285483, x.modPow(e, m));
 }
 
+// TODO(regis): Remove once even modulus is implemented.
+UnimplementedEvenModulusModInverse(x, m) {
+  Expect.equals(true, m.isEven);
+  try {
+    x.modInverse(m);
+    Expect.fail("Did not throw UnimplementedError");
+  } on UnimplementedError catch (e) {
+  }
+}
+
+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;
+  UnimplementedEvenModulusModInverse(x, m);
+  x = 10000000000000000001;
+  m = 12345678901234567890;
+  UnimplementedEvenModulusModInverse(x, m);
+  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;
+  UnimplementedEvenModulusModInverse(x, m);
+  x = 123456789012345678901234567891;
+  m = 123456789012345678901234567890;
+  UnimplementedEvenModulusModInverse(x, m);
+  x = 123456789012345678901234567891;
+  m = 123456789012345678901234567899;
+  Expect.equals(46296295879629629587962962962, x.modInverse(m));
+}
+
 testBigintNegate() {
   var a = 0xF000000000000000F;
   var b = ~a;  // negate.
@@ -254,6 +328,7 @@ main() {
   testBigintDiv();
   testBigintModulo();
   testBigintModPow();
+  testBigintModInverse();
   testBigintNegate();
   testShiftAmount();
   Expect.equals(12345678901234567890, (12345678901234567890).abs());