If you're seeing this message, it means we're having trouble loading external resources for Khan Academy.

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


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

Step 1: Split A^B into smaller parts using exponent rules

2^90 = 2^50 * 2^40

Step 2: Calculate the mod C for each part

2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3

Step 3: Use modular multiplication properties to 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....