🚀 go-pugleaf

I was tinkering around with the RSA algorithm last night, using really
small primes (e.g., 13 and 17) to generate keys.  The idea was that I
only wanted to use a 16-bit modulus, so I could avoid doing any
extended precision arithmetic, and so I could do the exponentation via
a naive "compute x^y by looping and multiplying by x, y times
(remember, this is just a toy implementation, and it's not intended
to do any "real" work).  But I ran into a few snags:

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.

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)?

--Pat.