RSA is a methodology to send and read secure messages via encryption and decryption. This

is the paradigm. Alice wants to send a message $M$ to Bob. Bob chooses prime numbers $p$ and $q,$

and an encryption key $e.$ He computes $d=e^{-1}$mod$(p-1)(q-1).$ Bob sends $N=pq$ and $e$ to

Alice. Alice computes $y=M^e$modN and sends it to Bob. Bob computes $y^d$modN to recover

$M.$

$($a$)$ Suppose that when designing the keys, Bob uses $p=79$ and $q=29.$ He randomly chooses

a value of $e=5.$ Find the value of $d.$ Show your work.

$($b$)$ RSA uses the fact that $(M^e{)}^d-=$MmodN. Show why the equivalence is true. $($Hint: Try

to first find $(M^e{)}^d$modp and $(M^e{)}^d$modq using Fermat's Little Theorem$).$