#!/usr/bin/env python

import math

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def CRT(key, p, q, n, m):
    keyP = key % (p-1)
    keyQ = key % (q-1)
    qInv = modinv(q, p)
    m1 = math.pow(m, keyP) % p
    m2 = math.pow(m, keyQ) % q
    h = qInv * (m1 - m2) % p
    m = m2+(h*q)
    return m

p = 3
q = 11
n = p*q             #33
phi = (p-1)*(q-1)   #20
e = 7
d = modinv(e, phi)  #3

m = 6

enc = math.pow(m, e) % n
print "Encrypted: ", enc
dec = CRT(d, p, q, n, enc)
print "Decrypted: ", dec