Find $k$ that will make $a^2-kN=b$ to be divisible by $p_1,p_2...p_s$ for some $a$

Question

$$a^2-kN=b$$

Where $N$ is a positive big integer and $a,k,b$ are integers, not necessarily big or positive.

How to compute a $k$ that will make the primes $p_1,p_2...p_s$ to be a quadratic residue mod $kN$?

I need this to optimize the prime base in the quadratic sieve algorithm when factoring small numbers. It's beneficial to have many small primes in the factor base.