Program 2:

Since the numbers are allowed to be very very large, you need to be able to process very large integers.  The Java BigInteger class works very well for this.  Other languages may or may not have such a library.  If you want to write your own that's OK, and not particularly difficult.

However, when you use these libraries, restrict yourself to basic arithmetic.  For example, the Java BigInteger class has a powermod method built-in, which is the exact same thing as the encryption algorithm for RSA.  (a^b mod c)

Given e, find d.  (ed) % phi(n) = 1.

prime:  13,19  n = 247.  phi(n) = 216.

e = 35, what is d?

216                0
 35       6        1
  6       5        -6
  5       1        31
  1                -37

What we want is a d such that 0 <= d < phi(n).  There is exactly one such d that will work.  It is possible that this algorithm will give you a d that is out of range.  This is not a problem.

If your d is out of range but is still positive, when what you want is d % phi(n).

If your d is negative, phi(n) - ( (-d)%phi(n) )

(If d%phi(n) "could" be 0 (it can't in this case))

  phi(n) - ((-(d+1))%phi(n)) -1

If your BigInteger class handles negatives, (and Java's does) this will work fine.

In this case, d = 179.
If you are nervous about using negatives at all, this can still be done.

216                0
 35       6        1  0 - 6*1 = 0 + (-1)*6*1 = 0+215*6*1
  6       5        210   1 - 5*210  = 1 + (-1)*5*210 = 1+215*5*210
  5       1        31    210 - 1*31 = 210 + 215*1*31
  1                179