Last M digits of expression A^N

[Mensanator]

On Feb 5, 2:18 pm, Mark Dickinson <dicki... at gmail.com> wrote:
> On Feb 5, 8:14 pm, mukesh tiwari <mukeshtiwari.ii... at gmail.com> 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,

It doesn't do 'exactly' that. M is the number of digits.
If you want 17 digits, the third number should 10**17.
Using 17 directly will give you a 2-digit answer as shown.

Try this instead:

>>> pow(12345,67891,10**17)
50553131103515625


> if you give it three
> arguments:
>
> >>> pow(12345, 67891, 17)
> 10
> >>> 12345 ** 67891 % 17
>
> 10L
>
> (Though this won't work for negative N.)
>
> Mark