Overview. Write a program to implement the RSA public$-$key cryptosystem. The RSA $($RivestShamir$-$Adleman$)$ cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and the Windows operating system. It works by manipulating integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate huge integers $($hundreds of digits$).$ The built$-$in C$/$Java type int is only capable of dealing with $16$ or $32$ bit integers, providing little or no security. You will design, implement, and analyze an extended precision arithmetic data type that is capable of manipulating much larger integers, using BigInteger in Java or simply using Python. You will use this data type to write a client program that encrypts and decrypts messages using RSA.

Note: the training wheels are off on this assignment $-$ you're starting with a blank screen, not our code. This means that you must pay particular attention to the process of building up your program from scratch. Consider carefully how your program should be structured and how you are going to implement the various functions before plunging in$.$ Remember to thoroughly test and debug each function as you write it$.$

The RSA cryptosystem. The RSA public key cryptosystem involves three integer parameters $d,e,$ and $n$ that satisfy certain mathematical properties. The private key $(d,n)$ is known only by Bob, while the public key $(e,n)$ is published on the Internet. If Alice wants to send Bob a message $($e$.$g$.,$ her credit card number$)$ she encodes her message as an integer $M$ that is between $0$ and $n-1.$ Then she computes:

$E(M)=$Mmodn

and sends the integer $E(M)$ to Bob. As an example, if $M=2003,e=7,d=2563,n=3713,$ then Alice computes

$E(M)={2003}^7$mod$3713=129,350,063,142,700,422,208,187$mod$3713=746.$

When Bob receives the encrypted communication $E(M),$ he decrypts it by computing:

$M=E(M{)}^d$modn.

Continuing with the example above, Bob recovers the original message by computing:

$M={746}^{2563}$mod$3713=2003.$

To check your arithmetic, you may use Matlab, maple.

Part $1($extended precision arithmetic$).$ The RSA cryptosystem is easily broken if the private key $d$ or the modulus $n$ are too small $($e$.$g$.,32$ bit integers$).$ The built$-$in C types int and long can typically handle only $16$ or $32$ bit integers.

Your main challenge is to design, implement, and analyze an extended precision arithmetic data type that can manipulate large $($nonnegative$)$ integers. To make it easier to check your work, we recommend working with integers represented using familiar decimal $($base $10)$ notation. $($We note that you could achieve superior performance by using a base that is a power of $2,$ e$.$g$.,256$ or $32,768.)$

Your data type will support the following operations: addition, subtraction,

Random number generation. Implement a function Math. random$()$ that takes as input an integer $n$ and returns a pseudo$-$random extended precision integer of at most $n$ digits by choosing each digit at random. This will be useful in debugging the subsequent code, and also in analyzing its complexity. $*$ Parity. Implement the function $1$ sodd that takes an extended precision integer as input and return $1$ if and only if it is odd. You may assume that the base is even, so that this amount to checking the parity of the least significant bit.

Comparisons. Implement the following functions: XPgreater$(),$ XP$1$ess $(),$ and XPeq$().$ They should take two $(2$N$+1)-$digit extended precision integers as input and return $1$ if and only if the first integer is greater than $($less than, equal to$)$ the second.

Subtraction. Implement the functions X$?$sub $().$ It should take two $(2N+1)$ digit extended precision integers as input and return a third extended precision integer that is the difference of the two. You should check that the first integer is greater than or equal to the second before subtracting; otherwise output an error message.

Multiplication. Implement the function XPmu$1().$ It should take two extended precision integers as input and return a third extended precision integer that is the product of the two. Observe that if a and $b$ are $N-$digit integers, the product will have at most $2N$ digits.

Division. Integer division is the most complicated of the arithmetic functions. Here is one of the simplest algorithms to compu