$(1$ point$)$ In this problem we will crack RSA. Suppose the parameters for an instance of the RSA cryptosystem are $N=4661,e=5.(1$ point$)$ The speed of RSA hinges on the ability to do large modular exponentiations quickly.

While $e$ can be made small, $d$ generally cannot.

A popular method for fast modular exponentiation is the Square and Multiply algorithm.

Suppose that $N=19511$ and $d=3845.$ We want to use the Square and Multiply algorithm to quickly decrypt $y=17512.$

a$)$ Express $d$ as a binary string $($e$.$g$\mathrm{.}10110110).SQ\frac{,}{M}UL,SQ,SQ,SQ\frac{,}{M}UL,SQ,SQ\frac{,}{M}UL,SQ,SQ.$

c$)$ What is $x=y^d$modN $?$

We have obtained some ciphertext $y=1046.$

a$)$ Factor $N=4661$ into its constituent primes $p$ and $q.$

min$(p,q)=$

max$(p,q)=$

b$)$ Compute $(N).$

$(4661)=$

c$)$ Compute $d,$ the decryption exponent.

$d=$

d$)$ Decrypt $y=1046$ to find the plaintext.

$x=$