What's the most efficient algorithm to compute powers?

Question

I'm simulating the RSA protocol for public and private key setup through Python 3 and I have to deal with huge exponents. Since the pow(base,exp) doesn't seem to run in a reasonable time I've been trying to use different algorithms, but for now none seems to work.

Which is the most efficient algorithm by now to do that?

Answer 1

Calculate the binary powers of base modulo n by squaring the previous binary power e.g. base^2=base^1*base^1; base^4 = base^2*base^2

By binary I mean base^0, base^1, base^2, base^4, base^8 etc.

Then multiple the binary powers when the bit is set in the exponent.

E.g. exponent 9: base^9 = base^1 * base^8. All calculations are done in modulo n.

Find attached the pseudocode; I hope it is correct because it is untested;

//pseudocode
function myPower(base, exponent, n) {
    power = 1;
    binarypower = base;
    while(exponent>0) {
        if(exponent&1 != 0) {
            power = (binarypower * power) %n;
        }
        exponent = exponent>>1;
        if(exponent>0) {
            binarypower = (binarypower*binarypower)%n;
        }
    }
    return power;
}