Binary exponentation with modulo
The string manipulation is avoidable, by working with bits of the exponent directly:

def quad_pow(base, exponent, modul): 
    a = 1
    b = base

    while exponent:
        if exponent &amp; 1:
            a = (a * b) % modul
        b = (b * b) % modul
        exponent &gt;&gt;= 1
    return a