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


http://cstheory.stackexchange.com/questions/6755/fastreductionfromrsatosat answers this question directly. 


This is not a research level question, but it follows immediately from the NPhardness 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. 

