Pow and mod function optimization

I need to create an optimized function to count Math.pow(a,b) % c; in Javascript;

There's no problems while cou开发者_运维百科nting small numbers like:

Math.pow(2345,123) % 1234567;

But if you try to count:

Math.pow(2345678910, 123456789) % 1234567;

you'll get incorrect result because of Math.pow() function result that cannot count up "big" numbers;

My solution was:

function powMod(base, pow, mod){
    var i, result = 1;
    for ( i = 0; i < pow; i++){
        result *= base;
        result %= mod;
    }
return result;

Though it needs a lot of time to be counted;

Is it possible to optimized it somehow or find more rational way to count up Math.pow(a, b) % c; for "big" numbers? (I wrote "big" because they are not really bigIntegers);

---

Based on SICP.

function expmod( base, exp, mod ){
  if (exp == 0) return 1;
  if (exp % 2 == 0){
    return Math.pow( expmod( base, (exp / 2), mod), 2) % mod;
  }
  else {
    return (base * expmod( base, (exp - 1), mod)) % mod;
  }
}

This one should be quicker than first powering and then taking remainder, as it takes remainder every time you multiply, thus making actual numbers stay relatively small.

---

Your method is good so far, but you will want to do http://en.wikipedia.org/wiki/Exponentiation_by_squaring also known as http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

The idea is that x^45 is the same as (expanded into binary) x^(32+8+4+1), which is the same as x^32 * x^8 * x^4 * x^1

And you first calculate x^1, then x^2 == (x^1)^2, then x^4 == (x^2)^2, then x^8 == (x^4)^2, then...

---

you can also use the mountgomery reduction in combination with exponentiation which is largely useful for large exponents > 256:

http://en.wikipedia.org/wiki/Montgomery_reduction#Modular_exponentiation

It has also been implemented in this BigInteger Library for RSA-encryption:

http://www-cs-students.stanford.edu/~tjw/jsbn/