🚀 go-pugleaf

In article <AfATsxL0Bwx2F93KFX@transarc.com> Pat_Barron@transarc.com writes:

   1)  During the exponentiation, the numbers get *really* big.  Like, I
   was shocked at how quickly they got big.  Is there any shortcut for
   computing m^e mod n, without actually computing m^e first?  Like, can
   I loop somehow, accumulating partial results, until at the end I have
   the value m^e mod n, without having actually computed m^e first?  Even
   if I choose, say, 3 or 5 as the private key, the public exponent tends
   to be big enough that m^e is way beyond the capacity of a 32-bit
   unsigned integer.

Compute m^e mod n by repeated squaring and multiplication mod n.
Here is pseudo-C for it (warning, this routine may infringe RSA patent :-) )
   
int expmod (int x, int s, int n)  /* compute x^s mod n */
{
   int p;
   if (s == 0) return 1;
   p = expmod (x, s/2, n); /* an efficient version wouldn't recurse */
   p = p * p;
   if (s % 2 == 1) 
	p *= x;
   return p % n;
}

   2)  I chose the private key and public exponent by brute force.  Is
   a better way to choose the private key than to factor (p-1)(q-1) and
   choose something with no common factors?  Is there a better way to
   find the public exponent than just trying all the possible values
   until you find it (which is what I did)?

The public exponent should just be a random number between 3 and the modulus.

To tell if A and B have common factors, you don't have to factor either
A or B.  Just use the Euclidean GCD algorithm, which is very efficient.