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.



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.

  • $\begingroup$ Thanks! I suppose you could create a boolean circuit using the graph that encodes the factors, yes? $\endgroup$ – Tucker Haas Mar 19 '17 at 18:41
  • $\begingroup$ I'm not sure what you mean by "graph that encodes the factors". In a sense every integer encodes the multiset of its own factors, we just don't know how to enumerate the members (or output some member) in polynomial time. Do you mean the graph which I feed to the hamiltonain-path oracle? Then you could, I guess, but I don't see the purpose; you could just end the reduction sequence when you have a boolean circuit, rather than going back and forth an extra time. $\endgroup$ – Jonas Kölker Mar 20 '17 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.