Implement modInverse for an even modulus.

runtime/lib/bigint.dart

 // Copyright (c) 2014, 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.
 
 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 /*
  * Copyright (c) 2003-2005  Tom Wu
@@ skipping 1524 matching lines @@
       }
     }
     assert(!is1);
     return z._revert(r_digits, r_used)._toValidInt();
   }
 
   // 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 (_used == 0) return 0;
+    if (m == 1) return 0;
     m = m._toBigint();
-    // TODO(regis): Implement modInverse for an even modulus.
-    if (m.isEven) throw new UnimplementedError();
     var t = this;
-    if ((t._compare(m) >= 0) || t._neg) {
+    if (t._neg || (t._absCompare(m) >= 0)) {
       t %= m;
       t = t._toBigint();
     }
+    final bool ac = m.isEven;
     final t_used = t._used;
-    if (t_used == 0) {
-      return 0;  // No inverse.
-    }
+    if ((t_used == 1) && (t._digits[0] == 1)) return 1;
+    if ((t_used == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
     final m_digits = m._digits;
     final m_used = m._used;
-    final uv_len = m_used + (m_used & 1);
-    var v_digits = _cloneDigits(t._digits, 0, t_used, uv_len);
-    var u_digits = _cloneDigits(m_digits, 0, m_used, uv_len);
+    final tuv_len = m_used + (m_used & 1);
+    final t_digits = _cloneDigits(t._digits, 0, t_used, tuv_len);
+    var u_digits = _cloneDigits(m_digits, 0, m_used, tuv_len);
+    var v_digits = _cloneDigits(t_digits, 0, t_used, tuv_len);
 
-    // Variables b and d require one more digit for carry.
-    final bd_used = m_used + 1;
-    final bd_len = bd_used + (bd_used & 1);
-    var b_digits = new Uint32List(bd_len);
-    var d_digits = new Uint32List(bd_len);
-    bool b_neg = false;
-    bool d_neg = false;
-
+    // Variables a, b, c, and d require one more digit.
+    final abcd_used = m_used + 1;
+    final abcd_len = abcd_used + (abcd_used & 1) + 2;  // +2 to satisfy _absAdd.
+    var a_digits, b_digits, c_digits, d_digits;
+    bool a_neg, b_neg, c_neg, d_neg;
+    if (ac) {
+      a_digits = new Uint32List(abcd_len);
+      a_neg = false;
+      a_digits[0] = 1;
+      c_digits = new Uint32List(abcd_len);
+      c_neg = false;
+    }
+    b_digits = new Uint32List(abcd_len);
+    b_neg = false;
+    d_digits = new Uint32List(abcd_len);
+    d_neg = false;
     d_digits[0] = 1;
 
     while (true) {
       while ((u_digits[0] & 1) == 0) {
         _rsh(u_digits, m_used, 1, u_digits);
-        if ((b_digits[0] & 1) == 1) {
-          _absSub(m_digits, m_used, b_digits, m_used, b_digits);
-          b_neg = !b_neg;
-        }
-        _rsh(b_digits, m_used, 1, b_digits);
+        if (ac) {
+          if (((a_digits[0] & 1) == 1) || ((b_digits[0] & 1) == 1)) {
+            if (a_neg) {
+              if ((a_digits[m_used] != 0) ||
+                  (_compareDigits(a_digits, m_used, t_digits, m_used)) > 0) {
+                _absSub(a_digits, abcd_used, t_digits, m_used, a_digits);
+              } else {
+                _absSub(t_digits, m_used, a_digits, m_used, a_digits);
+                a_neg = false;
+              }
+            } else {
+              _absAdd(a_digits, abcd_used, t_digits, m_used, a_digits);
+            }
+            if (b_neg) {
+              _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+            } else if ((b_digits[m_used] != 0) ||
+                (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
+              _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+            } else {
+              _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+              b_neg = true;
+            }
+          }
+          _rsh(a_digits, abcd_used, 1, a_digits);
+        } else if ((b_digits[0] & 1) == 1) {
+          if (b_neg) {
+            _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+          } else if ((b_digits[m_used] != 0) ||
+                     (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
+            _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+          } else {
+            _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+            b_neg = true;
+          }
+        }
+        _rsh(b_digits, abcd_used, 1, b_digits);
       }
       while ((v_digits[0] & 1) == 0) {
         _rsh(v_digits, m_used, 1, v_digits);
-        if ((d_digits[0] & 1) == 1) {
-          _absSub(m_digits, m_used, d_digits, m_used, d_digits);
-          d_neg = !d_neg;
-        }
-        _rsh(d_digits, m_used, 1, d_digits);
+        if (ac) {
+          if (((c_digits[0] & 1) == 1) || ((d_digits[0] & 1) == 1)) {
+            if (c_neg) {
+              if ((c_digits[m_used] != 0) ||
+                  (_compareDigits(c_digits, m_used, t_digits, m_used) > 0)) {
+                _absSub(c_digits, abcd_used, t_digits, m_used, c_digits);
+              } else {
+                _absSub(t_digits, m_used, c_digits, m_used, c_digits);
+                c_neg = false;
+              }
+            } else {
+              _absAdd(c_digits, abcd_used, t_digits, m_used, c_digits);
+            }
+            if (d_neg) {
+              _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+            } else if ((d_digits[m_used] != 0) ||
+                (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+              _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+            } else {
+              _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+              d_neg = true;
+            }
+          }
+          _rsh(c_digits, abcd_used, 1, c_digits);
+        } else if ((d_digits[0] & 1) == 1) {
+          if (d_neg) {
+            _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+          } else if ((d_digits[m_used] != 0) ||
+                     (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+            _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+          } else {
+            _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+            d_neg = true;
+          }
+        }
+        _rsh(d_digits, abcd_used, 1, d_digits);
       }
       if (_compareDigits(u_digits, m_used, v_digits, m_used) >= 0) {
         _absSub(u_digits, m_used, v_digits, m_used, u_digits);
+        if (ac) {
+          if (a_neg == c_neg) {
+            var a_cmp_c =
+                _compareDigits(a_digits, abcd_used, c_digits, abcd_used);
+            if (a_cmp_c > 0) {
+              _absSub(a_digits, abcd_used, c_digits, abcd_used, a_digits);
+            } else {
+              _absSub(c_digits, abcd_used, a_digits, abcd_used, a_digits);
+              a_neg = !a_neg && (a_cmp_c != 0);
+            }
+          } else {
+            _absAdd(a_digits, abcd_used, c_digits, abcd_used, a_digits);
+          }
+        }
         if (b_neg == d_neg) {
-          if (_compareDigits(b_digits, m_used, d_digits, m_used) >= 0) {
-            _absSub(b_digits, m_used, d_digits, m_used, b_digits);
-          } else {
-            _absSub(d_digits, m_used, b_digits, m_used, b_digits);
-            b_neg = !b_neg;
+          var b_cmp_d =
+              _compareDigits(b_digits, abcd_used, d_digits, abcd_used);
+          if (b_cmp_d > 0) {
+            _absSub(b_digits, abcd_used, d_digits, abcd_used, b_digits);
+          } else {
+            _absSub(d_digits, abcd_used, b_digits, abcd_used, b_digits);
+            b_neg = !b_neg && (b_cmp_d != 0);
           }
         } else {
-          _absAdd(b_digits, m_used, d_digits, m_used, b_digits);
-          if ((b_digits[m_used] > 0) ||
-              (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
-            _absSub(b_digits, bd_used, m_digits, m_used, b_digits);
-          }
+          _absAdd(b_digits, abcd_used, d_digits, abcd_used, b_digits);
         }
       } else {
         _absSub(v_digits, m_used, u_digits, m_used, v_digits);
-        if (b_neg == d_neg) {
-          if (_compareDigits(d_digits, m_used, b_digits, m_used) >= 0) {
-            _absSub(d_digits, m_used, b_digits, m_used, d_digits);
-          } else {
-            _absSub(b_digits, m_used, d_digits, m_used, d_digits);
-            d_neg = !d_neg;
+        if (ac) {
+          if (c_neg == a_neg) {
+            var c_cmp_a =
+                _compareDigits(c_digits, abcd_used, a_digits, abcd_used);
+            if (c_cmp_a > 0) {
+              _absSub(c_digits, abcd_used, a_digits, abcd_used, c_digits);
+            } else {
+              _absSub(a_digits, abcd_used, c_digits, abcd_used, c_digits);
+              c_neg = !c_neg && (c_cmp_a != 0);
+            }
+          } else {
+            _absAdd(c_digits, abcd_used, a_digits, abcd_used, c_digits);
+          }
+        }
+        if (d_neg == b_neg) {
+          var d_cmp_b =
+              _compareDigits(d_digits, abcd_used, b_digits, abcd_used);
+          if (d_cmp_b > 0) {
+            _absSub(d_digits, abcd_used, b_digits, abcd_used, d_digits);
+          } else {
+            _absSub(b_digits, abcd_used, d_digits, abcd_used, d_digits);
+            d_neg = !d_neg && (d_cmp_ab != 0);
           }
         } else {
-          _absAdd(d_digits, m_used, b_digits, m_used, d_digits);
-          if ((d_digits[m_used] > 0) ||
-              (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-            _absSub(d_digits, bd_used, m_digits, m_used, d_digits);
-          }
+          _absAdd(d_digits, abcd_used, b_digits, abcd_used, d_digits);
         }
       }
       // Exit loop if u == 0.
       var i = m_used;
-      while ((i > 0) && (u_digits[i - 1] == 0)) {
-        --i;
-      }
+      while ((i > 0) && (u_digits[i - 1] == 0)) --i;
       if (i == 0) break;
     }
     // No inverse if v != 1.
-    for (var i = m_used - 1; i > 0; --i) {
-      if (v_digits[i] != 0) return 0;  // No inverse.
-    }
-    if (v_digits[0] != 1) return 0;  // No inverse.
+    var i = m_used - 1;
+    while ((i > 0) && (v_digits[i] == 0)) --i;
+    if ((i != 0) || (v_digits[0] != 1)) throw new RangeError("Not coprime");
 
     if (d_neg) {
-      _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+      if ((d_digits[m_used] != 0) ||
+          (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+        _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+        if ((d_digits[m_used] != 0) ||
+            (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+          _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+        } else {
+          _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+          d_neg = false;
+        }
+      } else {
+        _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+        d_neg = false;
+      }
+    } else if ((d_digits[m_used] != 0) ||
+               (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+      _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+      if ((d_digits[m_used] != 0) ||
+          (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
+        _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+      }
     }
     return new _Bigint(false, m_used, d_digits)._toValidInt();
   }
 }
 
 // Interface for modular reduction.
 class _Reduction {
   // Return the number of digits used by r_digits.
   int _convert(_Bigint x, Uint32List r_digits);
   int _mul(Uint32List x_digits, int x_used,
@@ skipping 259 matching lines @@
 
   int _mul(Uint32List x_digits, int x_used,
            Uint32List y_digits, int y_used,
            Uint32List r_digits) {
     var r_used = _Bigint._mulDigits(x_digits, x_used,
                                     y_digits, y_used,
                                     r_digits);
     return _reduce(r_digits, r_used);
   }
 }