# Alice wishes to send Bob the following message
x = 1976620216402300889624482718775150

# example taken from http://doctrina.org/How-RSA-Works-With-Examples.html
# Bob creates a public key
# 1) Bob chooses two large primes
p = 12131072439211271897323671531612440428472427633701410925634549312301964373042085619324197365322416866541017057361365214171711713797974299334871062829803541
q = 12027524255478748885956220793734512128733387803682075433653899983955179850988797899869146900809131611153346817050832096022160146366346391812470987105415233

n = p*q
phi_n = (p-1)*(q-1)
e = 65537
#e = p
gcd(phi_n, e)
d = inverse_mod(e, phi_n)
mod(d*e, phi_n)
print "Public key n = " + str(n)
print "Public key e = " + str(e)

y = power_mod(x, e, n)
print "ciphertext y = " + str(y)

xx = power_mod(y, d, n)
print "comparing messages"
xx
x