Generating 3SAT circuit for Integer factorization example

Question

I read somewhere that 3SAT can be used to solve Integer Factorization.

If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given the number 6, then the factors are 2 and 3.

Answer 1

First we reduce the task of factorization to finding any factor of $n$ (or showing that it's prime). Once we know how to do this, we divide $n$ by such an factor and repeat the process until all factors are broken down to primes, and this takes $O(\log n)$ steps.

Let $k=\lceil\log_2 n\rceil$ the number of bits in $n$.

Next, we design a binary multiplication circuit that accepts two $k$-bit numbers and produces $2k$-bit results. The size of the circuit is obviously polynomial in $k$.

To the output of the circuit we add a $2k$-bit comparator that returns true if the result is equal to $n$ and false otherwise. We also add comparators to the inputs that check that the inputs are $>1$. So the combined circuit takes two $k$-bit numbers and returns true if they're both $>1$ and their product is equal to $n$.

Such a circuit can be described by a propositional formula, so this way we convert it to SAT.

Finally, we convert it from SAT to 3-SAT by a standard procedure. The result will be a 3-SAT formula with $2k$ propositional variables. If it is satisfiable, the propositional variables will just encode two factors of $n$. If it's unsatisfiable it means that $n$ is prime.