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.
-
$\begingroup$ @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. $\endgroup$– Rick DeckerOct 1, 2016 at 16:18
-
$\begingroup$ en.wikipedia.org/wiki/Exponentiation_by_squaring, en.wikipedia.org/wiki/… $\endgroup$– D.W. ♦Oct 2, 2016 at 0:19
2 Answers
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 $
-
1$\begingroup$ You don't actually need to precompute the binary digits of $e$. You can do it as you step through the loop. $\endgroup$ Oct 1, 2016 at 13:36
-
1$\begingroup$ 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. $\endgroup$ Oct 1, 2016 at 13:59
-
$\begingroup$ 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. $\endgroup$ Oct 1, 2016 at 16:06