CNF Generator for Factoring Problems

Problem Detail: 

I've been reading these:

• Fast Reduction from RSA to SAT
• CNF Generator for Factoring Problems (Also have C code implementation)

I don't understand how the reduction from FACT to $3\text{-SAT}$ works. Are there any simple articles in which I can read about it?

My final goal is to eventually implement a reduction from $3\text{-SAT}$ to the undirected Hamiltonian circuit problem.

Asked By : Ilya_Gazman

Answered By : Realz Slaw

I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it?

Most of the reading material assumes several steps of knowledge.

• First, you should read about how logic circuits (logic gates) work.
• Optionally learn or use a simple multiplication algorithm. You might want to start with the long-multiplication algorithm that everyone learns in school.
• Then research and understand a multiplication circuit, and/or learn how to convert the chosen algorithm to a circuit.
• You should now know how to make a simple multiplication circuit (MULT). Next learn to extend it for $n$-bit numbers.
• Once you have a circuit, you can force the outputs of the circuit to the $N$ value you want to factor. You do this by taking the $n$ outputs, and point-wise xoring them together with your $N$ value. Set the final output to be true iff $N$ and the MULT output cancel each-other out. You can do this by first oring all the xor results; if they are all $0$, then the output matched $N$ (in this case, set the final output to be $1$, else $0$).
• Now you have $\text{Circuit-SAT}$. Learn about $\text{Circuit-SAT}$.
• $\text{Circuit-SAT}$ asks if there is an input that can satisfy the output. $\text{Circuit-SAT}$ is an NP-complete problem, that is almost directly convertible to $3\text{-SAT}$ (when you get to this step, you will understand this pretty easily)
• There is a straightforward reduction from $\text{Circuit-SAT}$ to $3\text{-SAT}$ available here: Convert Circuit SAT to 3-SAT

You can't get it all in one scoop without talking to someone in-person. Rather you should follow the steps, without skipping. Each of these has "simple" material to learn from; but you'll not find one that teaches you everything in one sitting from the very basics.

---

Also see Computer Organization - Module II, section 2.5.1 Array Multiplier, which implements a carry-save-array-multiplication circuit:

Looks a lot like grade-school multiplication, doesn't it ...

Each box is (FA means "Full adder", which is also on that page in section 2.2 Serial & Parallel Adder):

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16789