#!/usr/bin/env python

import sys

#Compute all primes between 0 and max
#Input:
#max: maximum size of primes. Type: Integer
#Output:
#primes: ordered list of the primes between 1 and max
def computePrimes(max):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
	return primes

# Compute a public key
# Input:
# p, q: primes. Type: integer. Constraints: p, q < 300, p != q
# Output:
# (n, e): tupel of integers representing the public key
def computePubKey(p, q):
	assert (p < 300)
    assert (q < 300)
    assert (p != q)
    # Note: we do not do any primality tests here!

    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    # n and e must be integers!
    return (n, e)
	
	

	
# e and phi(n) are input, both integers
# Compute a private key
# Input:
# e, phi(n): as in lecture. Type: integer.
# Output:
# d: private key. Type: integer
def computePrivKey(e, phi):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    # d is the private key, an integer
    return d


# gcd() uses eea()
# Input:
# a, b: numbers to work on. Type: integer
# Output:
# gcd: the gcd. Type: integer
def gcd(a, b):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    return gcd


# eea is the Extended Euclidean Algorithm
# Input:
# a, b: numbers to work on. Type: integer
# Output:
# (x, y): numbers for which ax + by = gcd(a,b) holds. Type: tupel of integers
def eea(a, b):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    return (x, y)



# Compute phi(n) if input is a product of two primes
# Input:
# p, q: primes. Type: integer
# Output:
# o: phi(n). Type: integer
def computePhi(p, q):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    return o



# Compute an encrypted message
# Input:
# m: the message. Type: integer. Constraint: m < n
# pubkey: public key. Type: tupel of integers (n, e)
# Output:
# ciphertext: encrypted message. Type: integer
def encrypt(m, pubkey):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    return ciphertext


# Decrypt an encrypted message
# Input:
# c: the ciphertext. Type: integer
# d: the private key. Type: integer
# n: the product of p and q. Type: integer
# Output:
# decryptedtext: the decrypted message. Type: integer
def decrypt(c, d, n):
    # [YOUR TASK STARTS HERE]

    # ...

    # [YOUR TASK ENDS HERE]
    return decryptedtext


# Use this if you want to test your program
# DO NOT CHANGE THE FORMAT OF COMMAND LINE CALL
def main():
    # we read from stdin
    # first prime number
    p1 = int(sys.argv[1])
    # second prime number
    p2 = int(sys.argv[2])
    # message to encode, given as an integer m < n = p1 * p2
    m = int(sys.argv[3])

    # DO NOT CHANGE THE OUTPUT FORMAT
    (n, e) = computePubKey(p1, p2)
    print "Pubkey:" + str(n) + "," + str(e)
    phi = computePhi(p1, p2)
    print "Phi:" + str(phi)
    d = computePrivKey(e, phi)
    print "PrivKey:" + str(d)
    c = encrypt(m, (n, e))
    print "m:" + str(m) + "->" + str(c)
    print "c:" + str(c) + "->" + str(decrypt(c, d, n))

# main()