Bonus Assignment

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()`.