I need to create an optimized function to count Math.pow(a,b) % c; in Javascript;
There's no problems while counting 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);

I need to create an optimized function to count Math.pow(a,b) % c; in Javascript;
There's no problems while counting 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);

• javascript

4 Answers 4

Based on SICP, "Example: Testing for Primality" 1.2.6.

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/

Iterative version

function powerMod(base, exp, mod) {
    let result = 1;
    // base = base % mod; // use this if base >= mod
    while (exp > 0) {
        if (exp & 1)  //odd number
            result = (result * base) % mod;
        exp = exp >> 1; //divide by 2
        base = (base * base) % mod;
    }
    return result;
}