Modular exponentiation

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.

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.

Last updated

Was this helpful?