RSA Encryption/Decryption

Pick large primes

{p=RandomPrime[10^20],q=RandomPrime[10^20]}

Compute their product, which is the modulus for the public key

n=p q

Pick a random number relatively prime to (p-1)(q-1).  This is the (public) encryption exponent.

While[GCD[e=RandomInteger[n],(p-1)(q-1)]≠1];e

Find the inverse of  e  mod  (p-1)(q-1).  This is the (private) decryption exponent.

d=PowerMod[e,-1,(p-1)(q-1)]

Make up a message and convert the characters to numerical codes.

mess=ToCharacterCode["Your Message Here"]

Then use these as the digits of a number in base 128.

x=FromDigits[mess,128]

Encrypt.

y=PowerMod[x,e,n]

Converting this back to characters looks like garbage, of course.

FromCharacterCode[IntegerDigits[y, 128]]

Decrypt.

z=PowerMod[y,d,n]

Convert back to characters and recover the original message.

FromCharacterCode[IntegerDigits[z,128]]

Pollard's Factoring Algorithm

(First we'll do a baby example)

n=RandomPrime[10^3]*RandomPrime[10^3]

f[x_]:=Mod[x^2+2,n]

y=z=y0=RandomInteger[n]

(We should evaluate this next line repeatedly until we see a factor)

{y = f[y], z = f[f[z]], GCD[y - z, n]}

...

Now we'll get serious!

n = RandomPrime[10^5]*RandomPrime[10^5]

y = z = y0 = RandomInteger[n]

Repeat 100 times and hope it's enough to see a factor.  If not, we should repeat some more.

Table[{y = f[y], z = f[f[z]], GCD[y - z, n]},{100}]//TableForm