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


2 Answers 2


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.

  • $\begingroup$ Hi, I understand yes that part that if it is satisfiable then that means that Q isnt prime, and that it has factors. But I am still having problems by what you mean we can read the evaluations of the bits, from what I understand is solving a SAT instance would only determine whether it is satisfiable or not, and not necessarily give an assignment, giving an assignment. $\endgroup$ Feb 25, 2022 at 16:43
  • $\begingroup$ I get the last part as well, and for that I think we could instead of having x and y as n and the product being 2n bit, we can have all of them as the same number of bits, of course this may make it harder to solve, but will be complete in terms that if it is unsatifiable then it is certain that it a prime number, is what I am explaining correct? $\endgroup$ Feb 25, 2022 at 16:47
  • $\begingroup$ continued from first comment Could you elaborate a bit more on that part? And also the binary search part? Thank you $\endgroup$ Feb 25, 2022 at 16:50
  • $\begingroup$ @khaledsabek If you want to work with just the Satisfiable/Unsatisfiable boolean, then there is that procedure to get a valuation by running more a linear number of extra SAT queries. I'd say that's up to you. It doesn't fundamentally change anything, so it's theoretically a boring extra step. It's also unnecessary in practice because real SAT solvers output a valuation as certificate of satisfiability. $\endgroup$
    – harold
    Feb 25, 2022 at 17:26
  • $\begingroup$ @harlod i understand that it may not be necessary but the sat solver I am planning on using doesnt give out an evaluation, which is why I am in the current situation. Could you explain to me those linear number of extra SAT queries? $\endgroup$ Feb 26, 2022 at 4:24

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.