Right - to elaborate, my point was that since:
1- it's easy to generate RSA-like challenges for factoring, a product of two large primes.
2- it's easy to turn these RSA-like challenges into instances of the SAT problem (the canonical NP-complete problem).
3- SAT problems can be reduced to any NP-complete problem.
4- these reductions are known, because the typical proof of NP-completeness is to provide a reduction from another NP-complete problem, which will ultimately end up with SAT if you follow the chain for long enough.
... it follows that it's not too hard to generate hard instances of any NP-complete problem, assuming that factoring itself is a hard problem.
