Implement the function fast modular exponentiation

Question

I am trying to implement the function fast modular exponentiation(b, k, m) which computes:
b^(2k) mod m using only around 2k modular multiplications.

I tried this method:

def FastModularExponentiation(b, k, m):
    res = 1
    b = b % m
    while (k > 0):
        if ((k & 1) == 1):
            res = (res * b) % m
        k = k >> 1
        b = (b * b) % m
    return res

but I am still stuck in same problem which is if I try b = 2, k = 1, m = 10, my code returns 22. However, the correct answer is:

2^(2^1) mod 10 = 2^2 mod 10 = 4

and I cannot find the reason why.

Drizzle

Answer 1

Update: I finally understood that you do not want regular modular exponentiation (i.e., b^k mod m), but b^(2^k) mod m (as you plainly stated).

Using the regular built-in Python function pow this would be:

def FastModularExponentiation(b, k, m):
    return pow(b, pow(2, k), m)

Or, without using pow:

def FastModularExponentiation(b, k, m):
    b %= m
    for _ in range(k):
        b = b ** 2 % m
    return b

If you know r = phi(m) (Euler's totient function), you could reduce the exponent first: exp = pow(2, k, r) and then calculate pow(b, exp, m). Depending on the input values, this might speed things up.

---

(This was the original answer when I thought you wanted, b^k mod m)

This is what works for me:

def fast_mod_exp(b, exp, m):
    res = 1
    while exp > 1:
        if exp & 1:
            res = (res * b) % m
        b = b ** 2 % m
        exp >>= 1
    return (b * res) % m

The only significant differences I spot is in the last line: return (b * res) % m and that my while loop terminates earlier: while exp > 1 (which should be the same thing you do - except it saves an unnecessary squaring operation).

---

Also note that the built-in function pow will do all that for free (if you supply a third argument):

pow(4, 13, 497)
# 445

Allegorical

the answer was: Expected result: 1399670962, got 5793163382 instead – Drizzle

that is the problem! the input is randomly chosen, I am trying many test cases and success but fail for three – Drizzle

I understand that but please check this link so you will know it – Drizzle

the function pow () did not work! after a lot of searching and trying the problem looks like in the 4th line just replaced the 1 with 2 and worked well, please edit your answer in order to check it as accepted and please do not down vote my question! and if you up voted it I'll appreciate it – Drizzle

that is the solution: ideone.com/NMXUPZ in case you are interested – Drizzle

Answer 2

    def fast_exponentiation(k, x, q):
        # make sure all variables are non-negative
        assert (k >= 0 and x >= 0 and q >=1)
        result = 1 # define a counter 
        while x:
            if x % 2 == 1:
                 result = (result * k) % q
            k = (k ^ 2) % q
            x >> = 1 # bit shift operator, dividing x by 2 ** y thus x >> 2 ** 1 = x / 2 
       return result

Highbred