When P and Q are big primes, N=PQ is difficult to factorize. My question is how difficult to factorize N if I know value S=(Q^2 mod P)? It is possible to select P and Q such that the difficulty of finding them (knowing S) is as equivalent to difficulty of factorizing a smaller N?
In other words. Suppose I need a cryptographic strength of 512 bits. I select P and Q each of about 256 bits long. But now given that S will be revealed, how much do I have to increase the size of Q to retain the strength similar to 512 bit in normal case? It is possible at all? Maybe if S is known then there is a simple method to find P and Q.