1
$\begingroup$

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.

$\endgroup$
2

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 $

$\endgroup$
3
  • 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.