# Generating 3SAT circuit for Integer factorization example

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.

• – vzn May 3 '13 at 4:26

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.

• Thank you. Do you by any chance know of a resource with illustrations? I learn better by seeing pictures. – Jane May 2 '13 at 11:48
• @Jane Yes, pictures would be a nice addition, but unfortunately I don't know such a resource. – Petr Pudlák May 2 '13 at 12:25