Integer/prime factorization to 3 SAT

Question

So essentially as the title says, I just want to understand how its done. I have a light idea from my own research, but its failing at one point, and I feel it maybe due to crucial point missing in my understanding.

My understanding is to form a multiplication circuit of 2 n-bit variables, so for ex. X0 x1 .. xn and also y0 y1 ... yn, and the output of this multiplication circuit should be put into a bit wise comparator circuit, with our number that we want to factor which is of size 2N bits. Then follows that we turn this circuit to sat through the tseitan transformation, and from there to 3sat.

Now here comes my problem, I don't understand how that could get me the factors of the number. I understand that a Satisfiable instance at most will let me know that this number is prime, since there is two number x and y, that when multiplied result in my number, but what are they? And what about the other numbers? Am I missing something or what am I misunderstanding?

Thank you

Answer 1

I understand that a Satisfiable instance at most will let me know that this number is prime

It's the other way around: if the instance is satisfiable, then the number of interest (let's call it $Q$) is not prime, and $x$ and $y$ are non-trivial divisors of $Q$. $Q = x \cdot y$ by definition. If there is no solution to that equation, then the instance is unsatisfiable. $x$ and $y$ need not be factors of $Q$ because they're not necessarily prime. When a SAT instance is satisfiable, you normally, at least in practice, get a specific valuation as proof, from which you can read off the values of $x$ and $y$. Even if you don't get that, you can find them by binary search: force the first bit to False and see whether the result is still satisfiable, etc.

Unfortunately with this exact set-up, using two n-bit variables and a 2n-bit $Q$, an unsatisfiable instance does not in general prove that $Q$ is prime, because $Q$ could be of the form $2P$ (with $P$ a prime), then there is a solution to $Q = x \cdot y$ but not in such a way that $x$ and $y$ both fit in n bits because $P$ would be $2n-1$ bits and there is no other factorization of $Q$. But you could make some assumptions about the factors or make one of the variables bigger.

Answer 2

You have to go back to the proof that factorisation is in NP: Problem: Given n >= 2, find a sequence n1, n2, … such that n is the product of the $n_k$ and each $n_k$ is a prime.

The “hint” that you need to check in polynomial time is the list of the $N_k$, plus for each one a proof that it is indeed prime. For example, 30 = 3 * 10 is not a correct factorisation.

And you need to turn both the product check and the primality tests into a 3 SAT instance.

(PS. It is now known that primality can be proven in polynomial time. But verifying primality given a proof is much easier).