It is no big secret that exponentiation is just multiplication in disguise. It is a short hand way to write an integer times itself multiple times and is especially space saving the larger the exponent becomes. In the same vein, a serious problem with calculating numbers raised to exponents is that they very quickly become extremely large as the exponent increases in value. The following rule provides a great computational advantage when doing modular exponentiation.
The rule for doing exponentiation in modular arithmetic is:
This states that if we take an integer , raise it to an integer power and calculate the result modulo we will get the same result as if we had taken modulo first, raise it to , and calculate that product modulo .