3
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Do you know the factorization of the integer $N$? $\endgroup$ – ddddavidee Nov 16 '14 at 12:29
  • $\begingroup$ I do not know the prime factors of $N$ . $\endgroup$ – hanugm Nov 16 '14 at 12:46
  • $\begingroup$ So you cannot generate a such element $u$. The problem to distinguish between quadratic residues mod N and pseudo quadratic elements is infeasible for a large enough N. $\endgroup$ – ddddavidee Nov 16 '14 at 12:54
  • $\begingroup$ You can only generate a element and test if its Jacobi symbol is 1 or not. $\endgroup$ – ddddavidee Nov 16 '14 at 12:55
  • $\begingroup$ Sorry, I think I took a mental shortcut, actually you want to generate such element, so you can easily generate a square. $\endgroup$ – ddddavidee Nov 16 '14 at 22:32
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Yes, our answers are pretty close; we both provide ways to do it, given a little bit of help from the key generator. With you, the help is an example value of $s$; with mine, it's asking him to ensure $p \equiv q \equiv 3 \bmod 4$ (and with that, we can find a value of $s$ ourselves) $\endgroup$ – poncho Nov 16 '14 at 20:48
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.