Problem Detail: 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.
Asked By : Jane
Answered By : Petr Pudlák
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=lceillog_2 nrceil$ 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11718
