Alice$$s RSA public key is P $=($e$,$n$)=(7,4891).$ Bob sends Alice the message by encoding it as follows. First he assigns numbers to characters: A is $7,$ B is $8,...,$ Z is $32,$ a blank is $33,$ quotation marks: $34,$ a coma: $35,$ a period: $36,$ an apostrophe: $37.$ Then he uses RSA to encode each number separately.

Bob$$s encoded message is:

$161940492672142784539157022468493912672185545371427$

$3911427378020722361207284518557251427279639118553780$

$37803914049267220724462267239120722488391207223611689$

$2246248824882072380437801427154539172526721427845391$

$404926721855725142745371427464839146481427236118552072$

$84524881545391267222464049142745371427464839120722361$

$16894648224638041855380437801427154539123618492488725$

$3913804142739172526721427391725464884972526724522$

$1619$

Decode Bob$$s message. Notice that you only know Alice$$s public key, but don$$t know the private key. So you need to $$break$$ RSA to decrypt Bob$$s message. For the solution, you need to provide the following:

$($a$)$ Describe step by step how you arrived at the solution: show how to find p and q$,\backslash$phi $($n$)$ and d$.$

$($b$)$ Show your work for one integer in the message $($M $=2218)$: the expression, the decrypted integer, the

character that it is mapped to$.$

$($c$)$ To decode the remaining numbers, you need to write a program in C$++($see below$),$ test it in Grade$-$ scope, and append the code to HW $2,$ Problem $2$ solutions.

$($d$)$ Give the decoded message $($in integers$).$

$($e$)$ Give Bob$$s message in plaintext. What does it mean and who said it$?$

For part $($c$).$ Your program should :

$($i$)$ Take three integers, e$,$ n $($the public key for RSA$),$ and m $($the number of characters in the message$)$ as input to your program. Next, input the ciphertext.

$($ii$)$ Test whether the public key is valid. If not, output a single line $$Public key is not valid!$$ and quit the program.

$($iv$)$ If the public key is valid, decode the message.

$($v$)$ Output p and q$,\backslash$phi $($n$)$ and d$.$

$($vi$)$ On a new line, output the decoded message in integers.

$1$

$($vii$)$ On a new line, output the decoded message in English. The characters should be all uppercase. You can assume that the numbers will be assigned to characters according to the mapping above.