Add modPow tests.

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 1060 matching lines @@
   //             concatenated quotient and normalized remainder.
   // Output:
   //   r_digits[0..r_used-1]: positive remainder.
   // Returns r_used.
   static int _remDigits(Uint32List x_digits, int x_used,
                         Uint32List y_digits, int y_used, Uint32List ny_digits,
                         int nsh,
                         Uint32List yt_qd,
                         Uint32List t_digits,
                         Uint32List r_digits) {
-    assert(y_used > 0 && x_used >= y_used);
     // Initialize r_digits to normalized positive dividend.
     var r_used = _lShiftDigits(x_digits, x_used, nsh, r_digits);
     // For 64-bit processing, make sure y_used, i, and j are even.
     assert(y_used.isEven);
     var i = r_used + (r_used & 1);
     var j = i - y_used;
     var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits);
     // Explicit first division step in case normalized dividend is larger or
     // equal to shifted normalized divisor.
     if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) {
@@ skipping 246 matching lines @@
     return other._toBigint()._compare(this) == 0;
   }
 
   // Returns pow(this, e) % m, with e >= 0, m > 0.
   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;
-    e = e._toBigint();
     m = m._toBigint();
     final m_used = m._used;
     final m_used2p2 = 2*m_used + 2;
     final e_bitlen = e.bitLength;
     if (e_bitlen <= 0) return 1;
-    if ((e is! _Bigint) || m.isEven) {
-      _Reduction z = (e_bitlen < 8 || m.isEven) ?
+    final bool cannotUseMontgomery = m.isEven || _abs() >= m;
+    if (cannotUseMontgomery || e_bitlen < 64) {
+      _Reduction z = (cannotUseMontgomery || e_bitlen < 8) ?
           new _Classic(m) : new _Montgomery(m);
-      // TODO(regis): Should we use Barrett reduction for an even modulus?
+      // TODO(regis): Should we use Barrett reduction for an even modulus and a
+      // large exponent?
       var r_digits = new Uint32List(m_used2p2);
       var r2_digits = new Uint32List(m_used2p2);
       var g_digits = new Uint32List(m_used + (m_used & 1));
       var g_used = z._convert(this, g_digits);
       // Initialize r with g.
       var j = g_used + (g_used & 1);  // Copy leading zero if any.
       while (--j >= 0) {
         r_digits[j] = g_digits[j];
       }
       var r_used = g_used;
       var r2_used;
       var i = e_bitlen - 1;
       while (--i >= 0) {
         r2_used = z._sqr(r_digits, r_used, r2_digits);
         if ((e & (1 << i)) != 0) {
           r_used = z._mul(r2_digits, r2_used, g_digits, g_used, r_digits);
         } else {
           var t_digits = r_digits;
           var t_used = r_used;
           r_digits = r2_digits;
           r_used = r2_used;
           r2_digits = t_digits;
           r2_used = t_used;
         }
       }
       return z._revert(r_digits, r_used)._toValidInt();
     }
+    e = e._toBigint();
     var k;
     if (e_bitlen < 18) k = 1;
     else if (e_bitlen < 48) k = 3;
     else if (e_bitlen < 144) k = 4;
     else if (e_bitlen < 768) k = 5;
     else k = 6;
     _Reduction z = new _Montgomery(m);
     var n = 3;
     final k1 = k - 1;
     final km = (1 << k) - 1;
@@ skipping 186 matching lines @@
     var dl = digits[i] & _Bigint._DIGIT2_MASK;
     args[_MU] =
         (dl*rhol + (((dl*rhoh + dh*rhol) & MU_MASK) << _Bigint._DIGIT2_BITS))
         & _Bigint._DIGIT_MASK;
     return 1;
   }
 
   // r = x*R mod _m.
   // Return r_used.
   int _convert(_Bigint x, Uint32List r_digits) {
+    // Montgomery reduction only works if abs(x) < _m.
+    assert(x._abs() < _m);
     var r = x._abs()._dlShift(_m._used)._rem(_m);
     if (x._neg && !r._neg && r._used > 0) {
       r = _m._sub(r);
     }
     var used = r._used;
     var digits = r._digits;
     var i = used + (used & 1);
     while (--i >= 0) {
       r_digits[i] = digits[i];
     }
@@ skipping 87 matching lines @@
     var neg_norm_m = _Bigint._ONE._dlShift(nm_used)._sub(_norm_m);
     if (neg_norm_m._used < nm_used) {
       _neg_norm_m_digits =
           _Bigint._cloneDigits(neg_norm_m._digits, 0, nm_used, nm_used);
     } else {
       _neg_norm_m_digits = neg_norm_m._digits;
     }
     // _neg_norm_m_digits is read-only and has nm_used digits (possibly
     // including several leading zeros) plus a leading zero for 64-bit
     // processing.
-    _t_digits = new Uint32List(2*nm_used);
+    _t_digits = new Uint32List(2*nm_used + 2);
   }
 
   int _convert(_Bigint x, Uint32List r_digits) {
     var digits;
     var used;
     if (x._neg || x._compare(_m) >= 0) {
       var r = x._rem(_m);
       if (x._neg && !r._neg && r._used > 0) {
         r = _m._sub(r);
       }
@@ skipping 34 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);
   }
 }