Reduction Algorithm from Prime Factorization To Hamiltonian Path Problem How would you go about creating a reduction algorithm that would allow you to solve prime number factorization using Hamiltonian path finding?
Context: I was reading on P vs. NP and it heavily relies on the fact that NP-complete problems can be reduced to one another. I also saw lots of discussion on RSA and other cryptography being broken if we found a polynomial time algorithm for something like Hamiltonian paths. I am wondering how one could crack RSA given a black box that determined whether a Hamiltonian path was present and what that path was.
Thanks!
 A: Here's one approach which applies some basic definitions and long-established theory (without delving into those):


*

*Construct a non-deterministic polynomial-time turing machine which, when given an $n$ and $k$ accepts if there exists some $m$ where $1 < m < k$ and $m$ divides $n$, or rejects otherwise.  Find out some particular polynomial which bounds the execution time of this machine.


Ideally you would use this turing machine to do a binary search on the set $\{1, \ldots, n\}$ to extract a factor of $n$. Then divide $n$ by this factor and repeat until you have a full factorization.
However, you don't have a way of executing non-deterministic turing machines directly.  So instead do the following:


*

*For each query $(n, k)$, use the Cook/Levin reduction (See the Cook-Levin theorem) to construct a boolean circuit which is satisfiable iff the turing machine accepts $(n, k)$.

*Use the reduction from Circuit-SAT to 3-SAT to convert the circuit into a formula.

*Use the reduction from 3-SAT to Hamiltonian Path to convert the formula into a graph.

*Use your Hamiltonian Path oracle to tell you whether the graph has a hamiltonian path.

*Since reductions are answer-preserving, the answer it gives is the same as the answer to the question of whether $n$ has a non-trivial factor less than $k$.


An approach that probably leads to smaller graphs is to directly construct a boolean circuit (or formula) which is satisfiable iff $(n, k)$ is a yes-instance of the has-nontrivial-factor problem.
