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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\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.

$\endgroup$
0

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.