An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers (using a poly-time algorithm) which are very hard (takes more than poly-time) to factor, but using a quicker method and not necessarily deriving the prime factors.
[edit]
I'm aware of probabilistic primality tests. Nevertheless, I want a more efficient method than finding 2 primes and multiplying them.