Is it hard to find a big random easy to factor number?
Yes, this is feasible. Just generate sufficiently many nonce, rnd values, and you will eventually stumble upon a prime (or a number that can be factored into a large prime and a number of small prime factors). This is how most probabilistic prime generators operate.