On the other hand, if \(n=2^k\) then we can compute \(a^n\) by successive squaring with only \(k\) multiplications: \[\begin{aligned} a^2 &=a\cdot a \\ a^{2^2} &=\left(a^2\right)^2=a^2\cdot a^2 \\ a^{...On the other hand, if \(n=2^k\) then we can compute \(a^n\) by successive squaring with only \(k\) multiplications: \[\begin{aligned} a^2 &=a\cdot a \\ a^{2^2} &=\left(a^2\right)^2=a^2\cdot a^2 \\ a^{2^3} &=\left(a^{2^2}\right)^2=a^{2^2}\cdot a^{2^2} \\ \vdots \quad & \qquad \vdots \\ a^{2^k} &=\left(a^{2^{k-1}}\right)^2=a^{2^{k-1}}\cdot a^{2^{k-1}}\end{aligned}\] Note that the fact that \[2^k=\left(2^{k-1}\right)2=2^{k-1}+2^{k-1},\nonumber \] together with the exponent laws \[\left(a^n\right)^…
