1
$\begingroup$

Question: Given integers a and b and assuming that the only operation available is modular multiplication, show how to compute, C = a^b mod p using the minimal number of modular multiplications.

  • 0
    There are lots of references at [A003313](http://oeis.org/A003313)2012-09-24

2 Answers 2

1

Assuming you want an answer that depends only on $b$ (various ad hoc shortcuts might be possible by exploiting the value of $a$ or $p$), then this is known as the addition chain problem.

It's safe to call this non-trivial to compute exactly for general $b$, although it can be approximated. Knuth gives a fairly compact representation for $b < 149$ (can be found on this informative survey page). See A003313 in OEIS for more references and tables of values.

  • 0
    @Siva Why would converting $b$ to binary make any difference to the difficulty?2012-09-24
0

One approach could be to express $b=\sum_{0\le r\le n}c_r2^r$ where $c_r$ are $0$ or $1$.

Then calculate $a^{2^r}\pmod p$ starting from $r=0$ using $a^{2^r}=(a^{2^{r-1}})^2$ and take the product of the residues where $c_r=1$

One example is available here.

  • 0
    @Siva: if $b$ is a power of $2$, you get there with repeated squaring: $a, a^2, a^4, a^8 \ldots$ You can always use the approach suggested here, but it may not be optimal. $15$ is the first example where it is not, but there are many more. Finding the optimum is not easy, and this approach doesn't seem much worse.2012-09-24