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.
Finding minimal number of modular multiplications.
1
$\begingroup$
number-theory
-
0There are lots of references at [A003313](http://oeis.org/A003313) – 2012-09-24
2 Answers
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