RSA Algorithm, Outlined

Setup: once per identity
Step	Example	Notes
Choose P and Q, each prime	P = 257, Q = 683
Calculate X = PQ	X = 257 * 683 = 175531	Factoring 175531 is fairly easy. The UNIX factor command can factor it in well under 1 second. Factoring PQ becomes 'hard' if P and Q are 'large' (1000+ bits)
Calculate Y = (P-1)(Q-1)	Y = 256 * 682 = 174592	This number is used in the generation of D and E, and is discarded thereafter
Pick E such that it's relatively prime to Y	E = 17	Numbers of the form 1 + 2^N are convenient.
Pick D such that (DE % Y) = 1	D = 82161	(82161 * 17) % 174592 = 1
Your Public Key is E, X	17, 175531
Your Private Key is D, X	82161, 175531
Encrypt/Decrypt: once per message
Step	Example	Notes
Pick a message to encrypt, T	"Hi" = 0x4869 = 18537	The numeric value of the message must be < X, or data will be lost. Usual use of RSA is to encrypt a session key for a stream cipher, and then send the message encrypted with that key. Since cipher keys are typically < 128 bits, this is fine.
Encrypt (T) = (T ^ E) % X	(18537 ^ 17) % 175531 = {a big number} % 175531 = 88520	We pick E from numbers of the form 1 + 2^N because it makes this step computationally simpler.
Decrypt (M) = (M ^ D) % X	(88520 ^ 82161) % 175531 = {a huge number} % 175531 = 18537 = 0x4869 = "Hi"	Note that the 'hard' calculation (taking to a power that is very large) is on the private-key side. This is a happy thing, since it means that the owner of the key has the hard job

Obviously, a lot of work is going into making the op (A ^ B) % C a cheap operation. There are a lot of shortcuts that can be taken here, although the unix commands dc bc and perl are all capable of handling the task, if slowly. [e.g. "dc -e "88520 82161 ^ 175531 % p" takes ~16s on a 2Ghz P-IV]

Also, generating the primes in the first place is nontrivial. A recent paper asserts that is_prime(x) is in the P space, at O(N^12). (bits in N, not number itself) That's still very expensive.