Note that the solution to this problem is useful in the efficient implementation of the RSA algorithm, which is used widely for encryption.

For integers X and Y design an efficient $($log Y time$)$ iterative algorithm to compute X$^$Y $.$

Complete the following proof outline

$\{$x $=$ X $$ y $=$ Y $>=0\}?\{$z $=$ X$^$Y $\}$

You should assume that variables x$,$ y$,$ and z hold mathematical integers $$thus there is no overflow$$ and that the operations assignment, $+,-,\backslash$times $,-$:$,$odd$,$ and $$even$$ each take $1$ unit of time, as do any comparisons. Be sure to state the invariant of your loop.