# Modular exponentiation

##

Finally, let's explore the

Finally, let's explore the

**exponentiation property**:### A^B mod C = ( (A mod C)^B ) mod C

Often we want to calculate

Unfortunately,

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

Even if they didn't, it would take a

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

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