Finding minimal number of modular multiplications.

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.

-
There are lots of references at A003313 – Ross Millikan Sep 24 '12 at 17:03

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.

-
Thanks for your help. What if we convert b to binary? – Siva Sep 24 '12 at 17:15
@Siva Why would converting $b$ to binary make any difference to the difficulty? – Erick Wong Sep 24 '12 at 17:20

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.

-
This is not the minimum number. For instance, $a^{15}$ can be found in only $5$ multiplications by first computing $a^5$. The naive binary method uses $6$ multiplications. – Erick Wong Sep 24 '12 at 16:48
How have you computed $a^5? a, a^2,( a^3$ or $a^4)$ then $a^2\cdot a^3$ or $a\cdot a^4$? What about $a^{15}?$ – lab bhattacharjee Sep 24 '12 at 17:02
How about $a, a^2, a^4, a^5, a^{10}, a^{15}?$ – Ross Millikan Sep 24 '12 at 17:02
Thanks for your help. Help me if the condition is like b is binary. – Siva Sep 24 '12 at 17:16
@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. – Ross Millikan Sep 24 '12 at 17:38