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.

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.
