0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ There are also generators for CNF formulas available that encode integer factorization; the generated CNFs can then be used as a basis for generating 3SAT instances $\endgroup$
    – Manfred Weis
    Commented Jun 28 at 17:12

2 Answers 2

Reset to default
2
$\begingroup$

https://cstheory.stackexchange.com/questions/6755/fast-reduction-from-rsa-to-sat answers this question directly.

Improve this answer
$\endgroup$
0
$\begingroup$

This is not a research level question, but it follows immediately from the NP-hardness of 3SAT. The old book "Computers and Intractability" by Garey and Johnson used to be (i.e. there might be something better now) a good place to learn this topic. It's not something that can be explained in a few paragraphs. cs.stackexchange.com (the computer science stackexchange) is a better place for this type of question if you need further help.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .