Last M digits of expression A^N

mukesh tiwari mukeshtiwari.iiitm at gmail.com
Fri Feb 5 21:14:51 CET 2010


Hello everyone. I am kind of new to python so pardon me if i sound
stupid.
I have to find out the last M digits of expression.One thing i can do
is (A**N)%M but my  A and N are too large (10^100) and M is less than
10^5. The other approach   was  repeated squaring and taking mod of
expression. Is there any other way to do this in python more faster
than log N.

def power(A,N,M):
    ret=1
    while(N):
        if(N%2!=0):ret=(ret*A)%M
        A=(A*A)%M
        N=N//2
    return ret



More information about the Python-list mailing list