Syed Umar AnisJavascriptCalculate Modular Exponentiation (PowerMod) in Javascript (a^p % n)
Syed Umar AnisJavascriptCalculate Modular Exponentiation (PowerMod) in Javascript (a^p % n)
Javascript

# Calculate Modular Exponentiation (PowerMod) in Javascript (a^p % n)

Computing PowerMod is required to implement public-key cryptography as it is used for data encryption and decryption. Calculating it by regular arithmetic (i.e. calculating pth power of a) doesn’t work with large numbers used for encryption. That’s where PowerMod helps, it calculates the result by keeping the numbers significantly small and within range of the integer data type.

There are different algorithms for calculating PowerMod. The following is based on the pseudocode from Wikipedia, it is called ‘Right-to-left binary method’.

```// calculates   base^exponent % modulus
function powerMod(base, exponent, modulus) {
if (modulus === 1) return 0;
var result = 1;
base = base % modulus;     while (exponent &amp;amp;gt; 0) {
if (exponent % 2 === 1)  //odd number
result = (result * base) % modulus;
exponent = exponent &amp;amp;gt;&amp;amp;gt; 1; //divide by 2
base = (base * base) % modulus;
}
return result;
}
```

Use BigInt for large input values to the function. See comments for sample code with BigInt.

##### Hi, I’m Umar

1. Jorge Pina says:

thank you very much

2. James E. says:

Thanks a bunch for this! I’ve been looking all over for someone putting this algorithm in simple terms.

3. Steve Owens says:

Test this out on the following
modulus = 10^9 + 7
exponent = 395
base = 2

powerMod(base, exponent, modulus) => 877012756

1. Umar says:

For big numbers, we have to use BigInt

//source code with BigInt
function powerMod(base, exponent, modulus) {
if (modulus === BigInt(1)) return BigInt(0);
var result = BigInt(1);
base = base % modulus;
while (exponent > BigInt(0)) {
if (exponent % BigInt(2) === BigInt(1)) //odd number
result = (result * base) % modulus;
exponent = exponent >> BigInt(1); //divide by 2
base = (base * base) % modulus;
}
return result;
}

let result = powerMod(BigInt(2),BigInt(395), BigInt(1000000007));

console.log(result)