问题描述:

I am searching for an algorithm that allow me to compute ** (2^n)%d** with

The problem is that it's impossible to store `2^n`

in memory even with multiprecision libraries, but maybe there exist a trick to compute `(2^n)%d`

only using 32 or 64 bits integers.

Thank you very much.

Take a look at the Modular Exponentiation algorithm.

The idea is not to compute `2^n`

. Instead, you reduce modulus `d`

multiple times while you are powering up. That keeps the number small.

Combine the method with Exponentiation by Squaring, and you can compute `(2^n)%d`

in only `O(log(n))`

steps.

Here's a small example: `2^130 % 123 = 40`

```
2^1 % 123 = 2
2^2 % 123 = 2^2 % 123 = 4
2^4 % 123 = 4^2 % 123 = 16
2^8 % 123 = 16^2 % 123 = 10
2^16 % 123 = 10^2 % 123 = 100
2^32 % 123 = 100^2 % 123 = 37
2^65 % 123 = 37^2 * 2 % 123 = 32
2^130 % 123 = 32^2 % 123 = 40
```