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 p^{th} 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;gt; 0) {
if (exponent % 2 === 1) //odd number
result = (result * base) % modulus;
exponent = exponent &amp;gt;&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.

Learn more at: https://en.wikipedia.org/wiki/Modular_exponentiation

thank you very much

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

Test this out on the following

modulus = 10^9 + 7

exponent = 395

base = 2

powerMod(base, exponent, modulus) => 877012756

The correct answer is: 68717736

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)