from playcrypt.primitives import *
from playcrypt.tools import *
import time



def rsa_gen(sec_param):
    """
    Fill in this algorithm for creating RSA instances.
    @param sec_param: the bit length of the primes primes, p and q that should be generated.
    @return: list [N, e, d], where  N = p*q, and e is an integer that defines a permutation over Z_N^* through exponentiation, and d defines the inverse permutation of e. 
    """
    


def brute_force(N, e, y):
    """
    @param N: the rsa modulus
    @param e: an integer defining a permutation on Z_N^* through exponentiation.
    @param y: an element of Z_N^*
    @return: x such that x^e = y.  You may run in exponential time.  
    """

def e_root(N, e, d, y):
    """
    @param N: the rsa modulus
    @param e: an integer defining a permutation on Z_N^* through exponentiation.
    @param d: an integer defining the inverse permutation of e, also through exponentiation.
    @param y: an element of Z_N^*
    @return: x such that x^e = y.  You may NOT run in exponential time. 
    """
    


# Use this block for any printing/testing, do not leave stray print
# statements outside this block.
if __name__ == "__main__":
    for i in range(8,14):
        print("--------------------------------------------")
        print("Using primes of length ", i) 
        [N, e, d] = rsa_gen(i)
        y = random_Z_N_star(N)
        print(y)
        start_time = time.time()
        x = brute_force(N, e, y)
        print("--- Brute force time: %s  ---" % (time.time() - start_time))
        print(exp(x,e,N))

        start_time = time.time()
        x = e_root(N, e, d, y)
        print("--- polynomial time: %s ---" % (time.time() - start_time))
        print(exp(x,e,N))

    [N, e, d] = rsa_gen(512)
    y = random_Z_N_star(N)
    start_time = time.time()
    x = e_root(N, e, d, y)
    print("--- polynomial time: %s ---" % (time.time() - start_time))
    print(exp(x,e,N))