#!/usr/bin/python -t

import time, sys, os, random, math

def isprime (n):
	"check if n is prime"
	if n < 2 or (n > 2 and not n & 1): return 0
	si = int (math.sqrt (n))
	for j in xrange (2, si+1):
		if not n % j:
			return 0
	return 1

def nextprime (n):
	"get next prime"
	if n < 2: return 2
	while 1:
		n += 1
		if not n & 1:
			n += 1
		if isprime (n):
			return n

def factors (n):
	"return list of primefactors of n"
	on = n
	acc = 1
	f = []
	if isprime (n):
		f.append (n)
		return f
	c = 2
	while n > 1:
		if not n % c:
			f.append (c)
			acc *= c
			n //= c
			c -= 1
			ln = on / acc
			if isprime (ln):
				f.append (ln)
				return f
		c = nextprime (c)
	return f

def rndmirp (mi, ma):
	"return a random prime between mi and ma inclusively"
	while 1:
		x = random.randint (mi, ma)
		if isprime (x):
			return x

def gcd (a, b):
	v = a % b
	while v:
		a = b
		b = v
		v = a % b
	return b

def phi (p, q):
	return (p - 1) * (q - 1)

def func (e):
	yield e // 2

class Rsa:
	def __init__ (self, mi=0x70000000, ma=0x7fffffff):
		self.p = rndmirp (mi, ma)
		self.q = rndmirp (mi, ma)
		while not self.p ^ self.q:
			self.q = rndmirp (mi, ma)
		self.n = self.p * self.q
		self.m = phi (self.p, self.q)

		#generate E
		self.e = 0xffff+2
		while gcd (self.m, self.e) > 1:
			self.e += 2

		# generate D = (X*M + 1) / E is INT
		# note: D is the mod inverse of (E, M)
		self.d = 2
		while (self.d * self.m + 1) % self.e:
			self.d += 2
		self.d = (self.d * self.m + 1) / self.e

	def encrypt (self, msg):
		return pow (msg, self.e, self.n)

	def decrypt (self, msg):
		return pow (msg, self.d, self.n)

x = Rsa (1<<30, 1<<32)
print x.__dict__
for t in range (2, 100):
	c = x.encrypt (t)
	print t, '->', c, '->', x.decrypt (c)