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

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

Leave a Reply

Your email address will not be published.