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:

**smaller parts**using

**exponent rules**

2^**90** = 2^**50** * 2^**40**

**mod C**for

**each part**

**2^50** mod 13 = **1125899906842624** mod 13 = **4**

**2^40** mod 13 = **1099511627776** mod 13 = **3**

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