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 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. 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

thank you very much

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