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 TrueIn 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).

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

. - 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. - 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

- Implement an efficient solver for the discrete logarithm problem using
`quantum()`

.