Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
There are lots of references at A003313 –  Ross Millikan Sep 24 '12 at 17:03
add comment

2 Answers

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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