Reduction Algorithm from Prime Factorization To Hamiltonian Path Problem

Question

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!

Answer 1

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.