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:

And 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).