Checking both Quadratic residuosity and Jacobi symbol simultaneously and efficiently

Question

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 ?

Answer 1

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<y<(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.

Answer 2

If we are allowed to assume that $p \equiv 3 \pmod{4}$ and $q \equiv 3 \pmod{4}$ (where $p$ and $q$ are the prime factors of $N$), here is a method for generating a random non-QR with Jacobi symbol 1 (even if we don't know the values of $p$, $q$):

• Select a random value $r$ relatively prime to $N$

• Output $- r^2 \bmod N$

Here's how it works:

• A value $t$ will have Jacobi symbol 1 if both $\big({t\over p}\big)$ and $\big({t\over q}\big)$ are 1, or if they are both -1.

• A value $t$ will be a Quadratic residue if both $\big({t\over p}\big)$ and $\big({t\over q}\big)$ are 1 (or 0; we can ignore that case)

Hence, our task is to construct a random value where both $\big({t\over p}\big)$ and $\big({t\over q}\big)$ are -1.

Now, if we take a random value $r^2$, we have both $\big({r^2\over p}\big)$ and $\big({r^2\over q}\big)$ being 1 (because $r^2$ is obviously a QR.

Now, let us consider $-r^2$; since we have assumed that $r\equiv 3 \pmod{4}$, we know that $\big({r^2\over p}\big) = 1$ implies that $\big({-r^2\over p}\big) = -1$ (because for primes that are 3 mod 4, if $t$ is a QR, then $-t$ is not).

By the exact same logic, we see that $\big({-r^2\over q}\big) = -1$, and hence $-r^2$ is a random value with the properties we are looking for.