# Searching for efficient method to compute $a^n \bmod p$ for large numbers [duplicate]

I need an efficient algorithm with clear steps to compute $a^n \bmod p$ when $n$ is large enough and $p$ also. I'm looking for something equivalent to the built-in PowerMod function in Mathematica.

• @AntonTrunov. Yeah, I too discovered that, too. My choice of which to list as a duplicate was guided by which of the two answers I judged to be clearer. Oct 1, 2016 at 16:18
• – D.W.
Oct 2, 2016 at 0:19

The algorithm you are looking for is quick modular exponentiation.

It is based on the exponentiation property of modulus operator :

A^B mod C = ( (A mod C)^B ) mod C

for example we need to calculate 4^8 mod 7 (let us assume for the time being 4^8 is a large number and cannot be computed by available machines.)

we can then write

=(4^ 4 * 4 ^ 4) mod 7

=(4^4 mod 7 * 4^4 mod 7 )mod 7

= (256 mod 7 * 256 mod 7) mod 7

= 2

This algorithm doesn't only work for powers of 2 it works generally . We just need to write the power in its binary representation .

example :

3^31 mod 4

can be written as

3^(16+8+4+2+1) mod 4

you can see once we apply the exponentiation property to same the computations will be quite efficient.

You can use the Square and Multiply method:

Goal: Compute $y \equiv a^b \pmod{N}$

Step 1: $\text{Initialize }\\ x \leftarrow a \\ t ~\leftarrow 1$.

Step 2: Square and Multiply

$\text{while } b > 0: \\ \quad\quad \text{if } b \equiv 1 \pmod{2}: \\ \quad\quad\quad\quad t \leftarrow t \cdot x \pmod{N} \\ \quad\quad ~ x \leftarrow x^2 \pmod{N}\\ \quad\quad ~ b \leftarrow b \ \text{div} \ 2\\ \text{return } t$

• You don't actually need to precompute the binary digits of $e$. You can do it as you step through the loop. Oct 1, 2016 at 13:36
• At the second look I don't think this implementation works. You should start from the least significant digit. You also need a variable to store the successive powers of $x$: $x^1, x^2, x^4, ...$. And you need to store the result. Now it seems like those 2 variable got mixed up. Oct 1, 2016 at 13:59
• Looks good to me! I would probably save a line of code and used $b \leftarrow b \ \text{div} \ 2$ -- in that case $b \leftarrow b - 1$ is not need. Oct 1, 2016 at 16:06