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

sdk/lib/_internal/compiler/js_lib/js_number.dart

Index: sdk/lib/_internal/compiler/js_lib/js_number.dart
===================================================================
--- sdk/lib/_internal/compiler/js_lib/js_number.dart	(revision 43513)
+++ sdk/lib/_internal/compiler/js_lib/js_number.dart	(working copy)
@@ -366,6 +366,26 @@
     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".