AVK
0
Q:

fast exponentiation in python

def fast_exp(b, e, m): # Calculate b^e mod m
    init = 2
    powers = [b]
    # Calculate b powers until e
    while init <= e:
        powers.append((powers[-1]**2) % m)
        init *= 2
    binary = bin(e)[2:][::-1]
    product = 1
    # We can now multiply the correct powers
    for i in range(len(binary)):
        if binary[i] == '1':
            product *= powers[i]
            product %= m
    return product
0

New to Communities?

Join the community