Last M digits of expression A^N

Mark Dickinson dickinsm at gmail.com
Sun Feb 7 00:43:35 CET 2010


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

By the way, given that your M is fairly tiny compared with A and N, a
little bit of elementary number theory (e.g., Euler's theorem) could
save you a lot of time here.  For example,

pow(a, n, 10**5)

is equivalent to

pow(a, 5 + (n - 5) % 40000, 10**5)

for any n >= 5.  Not sure if this is the kind of thing you're looking
for.

--
Mark



More information about the Python-list mailing list