Show how to compute $2^{343}$ using the least multiplication. Show how to compute $2^{343}$ using the least multiplication.

One way to do this (and probably the way the prof wants) is exponentiation by squaring. Note that $x^{2n} = (x^n)^2$ and $x^{2n + 1} = (x^n)^2 \cdot x$. We can either break down $343$ into smaller pieces this way, but it's easier to think about starting at the bottom:
$$
\begin{array}{ccc}
Value & Computation & Multiplications & Total Multiplications \\
2^2 & (2^1)^2 & 1 & 1 \\
2^5 & (2^2)^2 \cdot 2 & 2 & 3 \\
2^{10} & (2^5)^2 & 1 & 4 \\
2^{21} & (2^{10})^2 \cdot 2 & 2 & 6 \\
2^{42} & (2^{21})^2 & 1 & 7 \\
2^{85} & (2^{42})^2 \cdot 2 & 2 & 9 \\
2^{171} & (2^{85})^2 \cdot 2 & 2 & 11 \\
2^{343} & (2^{171})^2 \cdot 2 & 2 & 13 \\
\end{array}
$$
How did I pick these numbers? Look at the binary expansion of $343 = 101010111_2$. Starting at the second-left digit, for each $1$, square and multiply, and for each zero, just square. Note that each computation only uses $2$ and the previous computation, so you don't have to store any auxilary results. If you really wanted to, you could write $2^{343}$ as (this is what starting from the top looks like):
$$ \left( 2^{171} \right)^2 \cdot 2 $$
$$ \left( \left( 2^{85} \right)^2 \cdot 2 \right)^2 \cdot 2 $$
$$ \left( \left( \left(2^{42} \right)^2 \cdot 2 \right)^2 \cdot 2 \right)^2 \cdot 2 $$
$$\vdots$$
$$ \left( \left( \left( \left( \left( \left( \left( 2^2 \right)^2 \cdot 2 \right)^2 \right)^2 \cdot 2 \right)^2 \right)^2 \cdot 2 \right)^2 \cdot 2 \right)^2 \cdot 2 $$
Because we don't store any auxilary results, this method is one multiplication slower than mjqxxxx's method, but this one generalizes much more cleanly. Which you should use depends on if you want a general method or just speed (in which case, perhaps a lookup table is appropriate?)
