I have to write a program to calculate `a**b % c`

where `b`

and `c`

are both very large numbers. If I just use `a**b % c`

, it's really slow. Then I found that the built-in function `pow()`

can do this really fast by calling `pow(a, b, c)`

.

I'm curious to know how does Python implement this? Or where could I find the source code file that implement this function?

If `a`

, `b`

and `c`

are integers, the implementation can be made more efficient by binary exponentiation and reducing modulo `c`

in each step, including the first one (i.e. reducing `a`

modulo `c`

before you even start). This is what the implementation of `long_pow()`

does indeed.

You might consider the following two implementations for computing `(x ** y) % z`

quickly.

**In Python:**

```
def pow_mod(x, y, z):
"Calculate (x ** y) % z efficiently."
number = 1
while y:
if y & 1:
number = number * x % z
y >>= 1
x = x * x % z
return number
```

**In C:**

```
#include <stdio.h>
unsigned long pow_mod(unsigned short x, unsigned long y, unsigned short z)
{
unsigned long number = 1;
while (y)
{
if (y & 1)
number = number * x % z;
y >>= 1;
x = (unsigned long)x * x % z;
}
return number;
}
int main()
{
printf("%d\n", pow_mod(63437, 3935969939, 20628));
return 0;
}
```

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow