Add modPow(int exponent, int modulus) method to int abstract class.

sdk/lib/_internal/compiler/js_lib/js_number.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.
 
 part of _interceptors;
 
 /**
  * The super interceptor class for [JSInt] and [JSDouble]. The compiler
  * recognizes this class as an interceptor, and changes references to
  * [:this:] to actually use the receiver of the method, which is
@@ skipping 348 matching lines @@
 
   int get bitLength {
     int nonneg = this < 0 ? -this - 1 : this;
     if (nonneg >= 0x100000000) {
       nonneg = nonneg ~/ 0x100000000;
       return _bitCount(_spread(nonneg)) + 32;
     }
     return _bitCount(_spread(nonneg));
   }
 
+  // Return pow(this, e) % m.

[floitsch, 2015/02/06 20:05:19]

Returns

[regis, 2015/02/06 21:46:54]

Done.

+  int modPow(int e, int m) {
+    if (e is! int || e < 0) throw new ArgumentError(e);
+    if (m is! int || m <= 0) throw new ArgumentError(m);

[Lasse Reichstein Nielsen, 2015/02/06 19:57:03]

Maybe not worth it, but you can use RangeError for the e<0 and m<=0 cases.

[regis, 2015/02/06 21:46:53]

Done.

+    if (e < 1) return 1;

[Lasse Reichstein Nielsen, 2015/02/06 19:57:03]

Why not 
  if (e == 0) ...

[regis, 2015/02/06 21:46:53]

Done.

+    int b = this;
+    if (b < 0 || b > m) {
+      b = b % m;
+    }
+    int r = 1;
+    while (e > 0) {
+     if ((e & 1) != 0) {
+       r = (r * b) % m;
+     }
+     e >>= 1;

[Lasse Reichstein Nielsen, 2015/02/06 19:57:03]

Using bit-operations restricts e to 2^32. Maybe use  
  if (e & 1 != 0) {
    ...
    e -= 1; 
  }
  e ~/ 2;
?

[floitsch, 2015/02/06 20:05:19]

I'm not sure it's worth it. But it would allow the exponent to go up to 53 bits.

[regis, 2015/02/06 21:46:54]

I replaced e & 1 != 0 by e.isOdd, since & is a bit operation. I am not sure if
using isOdd makes a difference in dart2js. Decrementing e is actually not
necessary.
I also replaced >>= 1 by ~/= 2.

+     b = (b * b) % m;

[Lasse Reichstein Nielsen, 2015/02/06 19:57:03]

I guess %m is expensive. Would it be worth it to do:
  b *= b;
  if (b > m) b %= m;
to avoid unnecessary modulos?

[floitsch, 2015/02/06 20:05:19]

I would hope that % is optimized for that case anyway.

[regis, 2015/02/06 21:46:53]

The vm is optimizing this case. I do not know if dart2js does it too. I left the
code as is (but fixed the bad indentation).

+    }
+    return r;
+  }
+
   // Assumes i is <= 32-bit and unsigned.
   static int _bitCount(int i) {
     // See "Hacker's Delight", section 5-1, "Counting 1-Bits".
 
     // The basic strategy is to use "divide and conquer" to
     // add pairs (then quads, etc.) of bits together to obtain
     // sub-counts.
     //
     // A straightforward approach would look like:
     //
@@ skipping 34 matching lines @@
 }
 
 class JSDouble extends JSNumber implements double {
   const JSDouble();
   Type get runtimeType => double;
 }
 
 class JSPositiveInt extends JSInt {}
 class JSUInt32 extends JSPositiveInt {}
 class JSUInt31 extends JSUInt32 {}