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 > 0) {
if (exponent % 2 === 1) //odd number
result = (result * base) % modulus;
exponent = exponent >> 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)