> For the complete documentation index, see [llms.txt](https://calnix.gitbook.io/zk-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://calnix.gitbook.io/zk-notes/abstract-math/modular-arithmetic/modular-exponentiation.md).

# Modular exponentiation

<figure><img src="/files/0ti4HPlhAPQC5o9zr1zZ" 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="/files/KUx2eEVklZri5Sx60BHC" 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>