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 true