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

runtime/lib/integers.dart

 // Copyright (c) 2012, 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.
 
 // TODO(srdjan): fix limitations.
 // - shift amount must be a Smi.
 class _IntegerImplementation extends _Num {
   // The Dart class _Bigint extending _IntegerImplementation requires a
   // default constructor.
 
@@ skipping 257 matching lines @@
   // Returns pow(this, e) % m.
   int modPow(int e, int m) {
     if (e is! int) throw new ArgumentError(e);
     if (m is! int) throw new ArgumentError(m);
     if (e < 0) throw new RangeError(e);
     if (m <= 0) throw new RangeError(m);
     if (e == 0) return 1;
     if (e is _Bigint || m is _Bigint) {
       return _toBigint().modPow(e, m);
     }
-    if (e < 1) return 1;
     int b = this;
     if (b < 0 || b > m) {
       b %= m;
     }
     int r = 1;
     while (e > 0) {
       if (e.isOdd) {
         r = (r * b) % m;
       }
       e >>= 1;
       b = (b * b) % m;
     }
     return r;
   }
+
+  // Returns 1/this % m, with m > 0.
+  int modInverse(int m) {
+    if (m is! int) throw new ArgumentError(m);
+    if (m <= 0) throw new RangeError(m);
+    if (m is _Bigint) {
+      return _toBigint().modInverse(m);
+    }
+    bool ac = m.isEven;
+    int u = m;
+    int v = this;
+    int a = 1,
+        b = 0,
+        c = 0,
+        d = 1;
+    while (u != 0) {
+      while (u.isEven) {
+        u >>= 1;
+        if (ac) {
+          if (!a.isEven || !b.isEven) {
+            a += this;
+            b -= m;
+          }
+          a >>= 1;
+        } else if (!b.isEven) {
+          b -= m;
+        }
+        b >>= 1;
+      }
+      while (v.isEven) {
+        v >>= 1;
+        if (ac) {
+          if (!c.isEven || !d.isEven) {
+            c += this;
+            d -= m;
+          }
+          c >>= 1;
+        } else if (!d.isEven) {
+          d -= m;
+        }
+        d >>= 1;
+      }
+      if (u >= v) {
+        u -= v;
+        if (ac) a -= c;
+        b -= d;
+      } else {
+        v -= u;
+        if (ac) c -= a;
+        d -= b;
+      }
+    }
+    if (v != 1) return 0;
+    if (d > m) return d - m;
+    if (d < 0) d += m;
+    if (d < 0) d += m;
+    return d;
+  }
 }
 
 class _Smi extends _IntegerImplementation implements int {
   factory _Smi._uninstantiable() {
     throw new UnsupportedError(
         "_Smi can only be allocated by the VM");
   }
   int get _identityHashCode {
     return this;
   }
@@ skipping 201 matching lines @@
   // Shift by mint exceeds range that can be handled by the VM.
   int _shrFromInt(int other) {
     if (other < 0) {
       return -1;
     } else {
       return 0;
     }
   }
   int _shlFromInt(int other) native "Mint_shlFromInt";
 }