Last M digits of expression A^N

Mark Dickinson dickinsm at
Fri Feb 5 21:18:42 CET 2010

On Feb 5, 8:14 pm, mukesh tiwari <mukeshtiwari.ii... at> wrote:
> 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

The built-in pow function does exactly this, if you give it three

>>> pow(12345, 67891, 17)
>>> 12345 ** 67891 % 17

(Though this won't work for negative N.)


More information about the Python-list mailing list