Issue 18005: faster modular exponentiation in some cases (original) (raw)

A trivial optimization can be made in pow(a, b, c) if b is even and c - a < a

In [1]: c = (1 << 1000000) + 1 

In [2]: a = c - 1234567

In [3]: b = 2

In [4]: %timeit pow(a, b, c)
1 loops, best of 3: 3.03 s per loop

In [5]: %timeit pow(c - a if c - a < (a >> 10) else a, b, c)
1000 loops, best of 3: 287 us per loop

This optimization is probably done in GMP, since using gmpy.mpz [5] is a bit slower than [4].