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