Exponentiation of large numbers can easily be implemented using exponentiation by squaring, which greatly reduces the number of steps it is needed for a given imput. Computing large exponents modulo a number is even faster and requires less memory, as it reduces the size of the resulting integer.
The following implementation works for both Python 3 and python 2 (although in Python 3 it will run faster):
Due to the modulo, the resulting function will be very fast: for example, it
calculates mesq(3**5**7, 11**17**3, 69) in a matter of milliseconds.
To get the idea behind, set the debug keyword argument to True. This will
show you how it actually calculates the result:
>>> mesq(7, 30, 5, True)
(7**30)%5 =
((7%5)**30)%5 =
((((7%5)**16)%5)*(((7%5)**8)%5)*(((7%5)**4)%5)*(((7%5)**2)%5))%5 =
((((((((((7%5)**2)%5)**2)%5)**2)%5)**2)%5)* \
(((((((7%5)**2)%5)**2)%5)**2)%5)* \
(((((7%5)**2)%5)**2)%5)* \
(((7%5)**2)%5) \
)%5 =
4And finally, if you’re wondering where would you need madular exponentiation, well, it comes in handy for example when generating Pratt certificates.
Update
Do not actually use this code. This is just an example. A way faster
implementation is the built-in pow(), which also accepts a third argument
(the modulo).