Compute PowerMod a^b%n

Q: List and compare the methods to compute where a, b, n are positive integers.

A: We have four methods. The first one is to naively compute the value but this is unprofessional and does not work if is very large that might overflow (e.g. a 32-bit or 64-bit cannot hold numbers like .

However, in Python, if you write math expressions like the following, it will still work, I guess the implementation does not bruteforce compute the

print 2**999999%147

The answer 50 is computed almost instantly. However, if you write.

print 2**999999

The python console almost hangs.. So it is obvious a hidden power-mod rule applies. So the first function is simple but yet only ‘OK’ in Python. This certainly does not work for some other programming languages if the code is translated and compiled as the way it looks e.g. compute and do the module operator.

def powermod1(a, b, n):
    return a**b%n

The second method is to apply multiplication and mod iteratively for . Decompose this into a for loop that do multiplication with number a, b times. In order to avoid that becomes large, use % at each step which does not affect the final result. Therefore, the following is memory-efficient.

def powermod2(a, b, n):
    r = 1
    for i in xrange(b):
        r = r * a % n
    return r

The third method and the fourth method are both based on the following property.

For any positive integers, a > 0, b > 0, n > 0, .

Therefore, the non-recurisve method decomposes the exponential value.

def powermod3(a, b, n):
    r = 1
    while b > 0:
        if b & 1 == 1:# odd number
            r = r * a % n
        b /= 2
        a = a * a % n
    return r

while the recursive presents the same idea.

def powermod4(a, b, n):
    if b == 1:
        return a % n
    r = powermod4(a, b / 2, n)
    r = r * r % n
    if (b & 1) == 1: # odd number
        r = r * a % n
    return r

Both approaches ensures the algorithm complexity of . The fourth method has one recurisve call that has half exponent (reduced complexity). For example, where and .

The following lists all these four methods and use package time to measure the performances. Be noted that we pick a relatively large exponent so a difference in time can be noticed. For small exponents, there is not much noticable performance difference on modern PCs.

#!/usr/bin/env python
# https://helloacm.com

from time import time

def powermod1(a, b, n):
    return a**b%n

def powermod2(a, b, n):
    r = 1
    for i in xrange(b):
        r = r * a % n
    return r
    
def powermod3(a, b, n):
    r = 1
    while b > 0:
        if b & 1 == 1:
            r = r * a % n
        b /= 2
        a = a * a % n
    return r

def powermod4(a, b, n):
    if b == 1:
        return a % n
    r = powermod4(a, b / 2, n)
    r = r * r % n
    if (b & 1) == 1:
        r = r * a % n
    return r

a = 2
b = 99999999
c = 147

starttime = time()
print powermod1(a, b, c)
print time() - starttime

starttime = time()
print powermod2(a, b, c)
print time() - starttime

starttime = time()
print powermod3(a, b, c)
print time() - starttime

starttime = time()
print powermod4(a, b, c)
print time() - starttime

One output on Intel i7, Win7-64 bit, 16GB, Python 2.7 is

134
0.713000059128
134
7.82999992371
134
0.00400018692017
134
0.00300002098083

The third and last methods present the best performances.

–EOF (The Ultimate Computing & Technology Blog) —