p = 5 q = 11, n = pq = 55, phi(n) = 40.

e = 37....d = 13    ed = 300+90+70+21 = 481; 481%40 = 1.


M = 3

The message has to be less than n, but it doesn't have to be relatively prime to anything.  Once you have computed n, e, and d,  the message just has to be less than n.


We will compute 3^37  mod 55       (M^e mod n)

3	37	3
9	18	3
26	 9	3*26=23
16	 4	23
36	 2	23
31	 1	31*23 = 713 = 53

Our message of 3 encodes to 53.

Somebody sent us the message 53.  We know that that our decrypt value is 13, but the world does not know this.


We will compute 53^13 mod 55    (M'^d mod n)

53	13	53
 4	 6	53
16	 3	16*53 = 848%55 = 23
36	 1	23*36=828%55 = 3



When you make your RSA key, and you need to pick your two primes,

Make sure they're both large.  If one of them is 198 digits long...and the other is the number 13...that's really easy to crack.

Also, make sure that one is much larger than the other.  Both must be large, but one should be really large.  BECAUSE if they close to each other, cracking algorithms often start with sqrt(n) and work down.  And if p and q are close to each other, then they are also close to sqrt(n).