The goal of this exercise is to work thru the RSA system in a simple case: We will use primes p = 71, q = 61 and form 71 ·61 = 4331. n = [This is typical of the RSA system which chooses two large...

Extracted text: The goal of this exercise is to work thru the RSA system in a simple case: We will use primes p = 71, q = 61 and form 71 ·61 = 4331. n = [This is typical of the RSA system which chooses two large primes at random generally, and multiplies them to find n. The public will know n but p and q will be kept private.] Now we choose our public key e = 13. This will work since gcd(13, (p – 1)(q – 1)) = gcd(13, 4200) = 1. [In general as long as we choose an 'e' with gcd(e, (p-1) (q-1))=1, the system will work.] Next we encode letters of the alphabet numerically say via the usual: (A=0,B=1,C=2,D=3,E=4,F=5,G=6,H=7,l=8, J=9,K=10,L=11,M=12,N=13,0=14,P=15,Q316,R=17, S=18,T=19,U=20,V=21,W=22,X=23,Y=24,Z=25.) We will practice the RSA encryption on the single integer 15. (which is the numerical representation for the letter "P"). In the language of the book, M=15 is our original message. The coded integer is formed via c = Me mod n. Thus we need to calculate 1513 mod 4331. This is not as hard as it seems and you might consider using fast modular multiplication. The canonical representative of 1513 mod 4331 is