Calculate Modular Exponentiation (PowerMod) in Javascript (a^p % n)
Computing PowerMod is required for implementing public-key cryptography as it is used to encrypt and decrypt data. 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. 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; }
Learn more at: https://en.wikipedia.org/wiki/Modular_exponentiation
2 Replies to “Calculate Modular Exponentiation (PowerMod) in Javascript (a^p % n)”
thank you very much
Thanks a bunch for this! I’ve been looking all over for someone putting this algorithm in simple terms.