Part $2($encryption and decryption$).$ Now it's time to put all your hard work to use. The encryption and decryption processes are identical, except that they involve different encryption$/$decryption keys. Write a program rsa.java that takes in one command line arguments $($the name of the encryption key$),$ reads in a decimal string from standard input, and applies the RSA function to the message. It should work as follows. In real applications, you might want to send an ASCII text message instead of a decimal integer; however, you are only responsible for handling decimal inputs.

RSA function. The key step is to implement the RSA function $($a$.$k$.$a$.$ modular exponentiation$)$: given three extended precision integers $a($the base$),b($the exponent$),$ and $n($the modulus$),$ compute $c=a^b$modn. You will implement this as the function xPrsa $()$ in $xp.c.$

A natural way to compute $c$ is to set $x=1$; then multiply it by $a,b$ times; then set $c=$xmodn. This method suffers from two serious performance bugs.

First, observe that if the inputs $a,b,$ and $n$ are $N-$digit decimal integers, then the intermediate result $x$ could contain as many as ${10}^N$ digits. To see the great importance of this, observe that if $N$ is $30,$ the intermediate result could consume a terrabyte of memory!

The second problem is that repeating anything $b$ times will be slow. If $b$ is even moderately large $($say $30$ decimal digits$),$ it will take centuries to execute, even on the fastest supercomputer.

We use two ideas to overcome the above obstacles. First, the following mathematical identity is useful to keep the intermediate numbers small.

xymodn$=((xmodn)**(ymodn))modn$

Second, we use the technique of divide$-$and$-$conquer or repeated squaring. We incorporate both ideas into the following pseudocode. This allows us to perform modular exponentiation in a reasonable amount of time $($when an appropriate base case is added$).$

$t=an(\frac{b}{2})$ mod $n$

$c=(t**t)$ mod $n$

$if(bis$ odd$)$

return $c(c**a)modn$

Note here that the division is integer division, and each of the intermediate computations is performed using extended precision arithmetic. The exponentiation computation is naturally implemented using recursion. As above, if $a,b,$ and $n$ are Ndigit numbers, then the intermediate results in this function will never have more than $2N$ digits. However, since $t^{**}t$ could be $2N$ digits long, the intermediate results in the mod $($division$)$ function might be as many as $2N+1$ digits. This explains why we allocate $2N+1$ digit.

Extra credit. Write a program that compute two large pseudo$-$random prime numbers $p$ and $q$ of a specified number of digits. Compute $=(p-1)(q-1),$ and select a small integer $e$ that is relatively prime with $.$ Use these to generate a public key $(e,n)$ and its companion secret key $(d,n).$