This is a very interesting question from a number-theoretic and computer scientific point-of-view.
However if you were thinking about practical ways one could 'backdoor' a system and have the backdoor transmit as little information back to the implanter, so as to allow factorization, there might be another way to look at it though. You could generate p,q using a PRNG seeded with, say, 256-bits. Then you could leak the 256-bits or some subset thereof. Or you could avoid leaking at all: Having generated the entropy of seeding the PRNG, you could replace some of the bits (say all except for 64 bits) with a hardcoded value or something that could be inferred in an attack scenario (derived from user-id, hardware serial numbers etc). Run that through a hash (probably not necessary if the PRNG is secure) and use that as the seed for the PRNG for generating p,q. Then you would be able to brute-force your way to p,q using only 2^64 operations even though the system seemingly has a much higher level of security. If this was embedded in hardware (i.e. a hardware RNG) where the hardcoded value could not be extracted, you would have this advantage to yourself - for everyone else it truly would require 2^256 operations.
Discovering the backdoor by others, would be possible by essentially 'brute-forcing' the RNG, exhausting the subspace it maps into and notice that you get duplicates more often than expected. You could try circumventions against that. So the attack works best if you have a much higher capacity for brute-force than is available to those who would audit the system.