For this assignment, you will submit a single Python source file
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
n in the same amount of time
that it takes to run
def quantum(f, g, n): for i in range(0,n): if f(i) != g(i): return False return TrueIn other words, if
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).
factor()that takes a single positive integer input
nand returns a non-trivial factor
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
n. Explain in detail why your algorithm still runs in polynomial time.
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