# Modular exponentiation

<figure><img src="https://1983523492-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F0nwEx8a60yETwfNYnenT%2Fuploads%2Fvj9CCxYjo1zepf6Bd65R%2Fimage.png?alt=media&#x26;token=953bac00-c04b-4c7b-beee-cf24c94fe399" alt=""><figcaption></figcaption></figure>

#### Example

Suppose we want to calculate **2^90 mod 13**, but we have a calculator that can't hold any numbers **larger than 2^50**.

<figure><img src="https://1983523492-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F0nwEx8a60yETwfNYnenT%2Fuploads%2FTMtwVYSGIHxPVkobpwWx%2Fimage.png?alt=media&#x26;token=d82d8b26-e016-4673-9386-bd2fb7909249" alt=""><figcaption></figcaption></figure>

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

* Fast modular exponentiation: [https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation)
