Q$1[16]$ Note that the solution to this problem is useful in the effi$-$ cient implementation of the RSA algorithm, which is used widely for encryption. For integers X and Y design an efficient $($log Y time$)$ iterative al$-$ gorithm to compute XY $.($a$)[8]$ Complete the following proof outline x $=$ X $$ y $=$ Y $>=0?$ z $=$ XY You should assume that variables x$,$ y$,$ and z hold mathematical integers $$thus there is no overflow$$ and that the operations as$-$ signment, $+,-,\backslash$times $,-$:$,$odd$,$ and $$even$$ each take $1$ unit of time, as do any comparisons. Be sure to state the invariant of your loop. $($b$)[4]$ List the boolean expressions that must be shown univer$-$ sally true $($according to the rules discussed in class$)($c$)[4]$ For each boolean expression from part $($b$),$ give a concise argument that it is universally trueQ$3[10]$ 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 algo$-$

rithm to compute $x^Y.$

Complete the following proof outline

$\{x=x^{{?}^{?}}y=Y0\}?\{z=x^Y\}$

You should assume that variables $x,y,$ and $z$ hold mathematical inte$-$

gers $-$ thus there is no overflow$-$ and that the operations assignment,

$,,+-,,$ 'odd', and 'even' each take $1$ unit of time, as do any compar$-$

isons. Be sure to state the invariant of your loop.