def GCD(n, m):
    while m!= 0:
        print(" "+str(n)+","+str(m))
        t=m
        m=n%m
        n=t
    return n

def not_mod(n,m):
    c=0
    d=1
    a=n
    b=m
    e=b/a
    f=b%a
    while f > 0:
        t = c - e * d
        if t>= 0:
          t = t % m
        else:
          t = m - ((-t) % m)
        c=d,d=t
        b=a,a=f
        e=b/a
        f=b%a
    return d

def powmod(n,m,o):
    t=n
    u=1
    v=m
    while v>0:
        if v%2:
            u=(u*t)%o
        t=(t*t)%o
        v=v/2
    return u

def rsaKeys(p,q):
    phi = (p-1)*(q-1)
    N = p*q
    e=3
    while GCD(e,phi) !=1:
        d=not_mod(e,phi)
        e=+2
    print("pub key: (e,n) "+e+","+N)
    print("priv key: (d,n) "+d+","+N)

def RSA(q,p,m):
    print(powmod(m,q,p))


print("Genreate RSA key pair - 1")
print("Encrypt message - 2")
choice = int(input("What do you want? "))
if choice:
    if choice == 1:
        print("q=?")
        q=int(input())
        print("p=?")
        p=int(input())
        rsaKeys(p,q)
    if choice == 2:
        q=int(input("q=? "))
        p=int(input("p=? "))
        m=int(input("message=? "))
        RSA(q,p,m)