Journey into cryptography

# Modular arithmetic

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