Bonus Assignment (back to full lecture notes)

For this assignment, you will submit a single Python source file aX.py.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts. You may reuse functions that you defined on previous assignments.

Suppose that you are given a black box quantum() that can compute the following Python function on any three inputs f, g, and n in the same amount of time that it takes to run f(n) and g(n):

def quantum(f, g, n):
    for i in range(0,n):
        if f(i) != g(i):
            return False
    return True
In other words, if f(n) and g(n) both run in polynomial time, then quantum(f,g,n) also runs in polynomial time (the above inefficient implementation is just for purposes of illustration and testing).

  1. Implement an efficient, polynomial-time algorithm factor() that takes a single positive integer input n and returns a non-trivial factor x of n (i.e., 1 < x < n) if it exists. Your implementation must invoke quantum() (it may invoke it multiple times, but no more than polynomially many times). That is, factor() must be a polynomial-time reduction from the factoring problem to quantum(). Hint: to better understand how quantum() might be able to help, try writing a function that can efficiently check if its input is a Carmichael number by using quantum().
  2. Modify your solution to part (a) so that it returns all the factors of the input n. Explain in detail why your algorithm still runs in polynomial time.
  3. Modify your solution from part (a) or part (b) so that it works with the following (slightly more realistic) version of quantum() (pseudocode provided; implement an inefficient test version of quantum() for more points):
    def quantum(f, g, n):
        if [f(i) for i in range(0,n)] is a permutation of [g(i) for i in range(0,n)]:
            return True
        return False
  4. Implement an efficient solver for the discrete logarithm problem using quantum().