If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# Modular exponentiation

Finally, let's explore the exponentiation property:
A^B mod C = ( (A mod C)^B ) mod C
Often we want to calculate A^B mod C for large values of B.
Unfortunately, A^B becomes very large for even modest sized values for B.

### For example:

2^90 = 1237940039285380274899124224
7^256 = 2213595400046048155450188615474945937162517050260073069916366390524704974007989996848003433 83794038078279445526231260759886736342594056001485602786638194645895120583737911647366324673350968 0721264246243189632348313601
These huge values cause our calculators and computers to return overflow errors.
Even if they didn't, it would take a long time to find the mod of these huge numbers directly.

### What can we do to reduce the size of terms involved and make our calculation faster?

Suppose we want to calculate 2^90 mod 13, but we have a calculator that can't hold any numbers larger than 2^50.
Here is a simple divide and conquer strategy:
smaller parts
exponent rules
2^90 = 2^50 * 2^40
mod C
each part
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
multiplication properties
combine the parts
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

### How can we calculate A^B mod C quickly if B is a power of 2 ?

How could we calculate 7^256 mod 13 using a calculator that can't hold numbers larger than 7^10 ?
We could split 7^256 into 25 parts of 7^10 and 1 part of 7^6, but this wouldn't be very efficient.
There is a better way....