Checking both Quadratic residuosity and Jacobi symbol simultaneously and efficiently I have to randomly generate a number $u$ such that $u \in J(N)-Q(N)$

where $J(N)$ denotes the set of elements less than $N$, whose Jacobi symbol value is equal to 1; and $Q(N)$ denotes the set of quadratic residues in $J(N)$ .

What is the best time-efficient way to generate it ?

I am thinking to generate like this:

1) Select an  positive integer $x$such that $(x+1)^2 \le {N}$.

2) Select any integer $y$ between $x^2 $ and $(x+1)^2 $ then check for $\big{(}\frac{y}{N}\big{)}=1$ and continue until we get .

The above method is not correct and counter example is provided in comments below .

Is it good and correct one ?
Given a composite $N$, it is asked to construct a random $u$ in $\mathbb Z_N^*$ with $\big({u\over N}\big)=+1$ that is not a square $\pmod N$.



The method proposed in the question does not work. Counterexample: $N=77$; $x=7$; $y=53$ which is such that $x^2&lt;y&lt;(x+1)^2\le N$ and $\big({y\over N}\big)=+1$. However $y$ is a quadratic residue since $53\equiv19^2\pmod {77}$. Problem is, it is asked that $y$ is not a square $\pmod N$, but the construction method proposed in the question only insures that $y$ is not a square in $\mathbb N$.



Here is a method that works assuming we know just one fixed $s$ in $\mathbb Z_n^*$ with $\big({s\over N}\big)=+1$ that is not a square $\pmod N$:


generate a random $x\in\{1\dots N-1\}$, until $\gcd(x,N)=1$;
compute and output $u=s\cdot x^2\bmod N$.


Using multiplicative properties of the Jacobi symbol, that $\big({s\over N}\big)=+1$ and $\big({x\over N}\big)\ne 0$, it follows from the construction of $u$ that $\big({u\over N}\big)=+1$. And because $x^2\bmod N$ is a non-zero quadratic residue, and $s$ is a non-zero non-quadratic residue, their product $u\pmod N$ is a  non-zero non-quadratic residue. $u$ is random-like because $x$ is random. I conjecture (without proof) that $u$ is uniform on the desired set; that would follow from proof that each distinct $x^2\bmod N$ with $\gcd(x,N)=1$ has an equal number of square roots $\pmod N$.

It remains to construct $s$. That seems impossible in the general case without knowing the factorization of $N$; however, in some practical cases, $N$ could be generated so that its factorization is known but secret, which allows to efficiently generate $s$; then $(N,s)$ can be made public and the factorization of $N$ forgotten.

Here is how the generation of $(N,s)$ could go:


generate two large random distinct primes $p$ and $q$;
compute $N=p\cdot q$;
generate a random $s\in\{1\dots N-1\}$ until $\big({s\over p}\big)=-1$ and $\big({s\over q}\big)=-1$;
output $(N,s)$.


Using multiplicative properties of the Jacobi symbol, $\big({s\over N}\big)=+1$. Because $\big({s\over p}\big)=-1$ and $p$ is prime, $s$ is not a quadratic residue $\pmod p$; thus $s$ is not a quadratic residue $\mod{p\cdot q}$.

Update following Poncho's answer: if $N=p\cdot q$ with $p$ and $q$ primes such that $p\equiv3\pmod4$ and $q\equiv3\pmod4$, then $s=N-1$ does the job.