1

I have a Zp finite field, and there are (p-1)/2 quadratic residues. So leaving 0 aside, there are exactly half quadratic residues.

Now, I need to create a 1-1 mapping between quadratic residues to other elements, i.e. for every x define its counterpart, which is not quadratic residue.

Is there an effective (sub-exponential) algorithm to do this?

valdo
  • 611
  • If you have the list of residues at hand, then you have its complement as well and you can match the first element of the first list to the first elements of the second list, etc. Or do you not assume given the list of quadratic residues? – Arnaud Mortier Jun 04 '18 at 23:26
  • 2
    All you need is a single non-residue, $a$. (if $r_1,\cdots, r_n$ is the list of residues then $ar_1,\cdots, ar_n$ is the list of non-residues.) – lulu Jun 04 '18 at 23:57
  • @lulu: Wow, thanks! This makes sense, I'll definitely try this! – valdo Jun 05 '18 at 04:48
  • @ArnaudMortier: I'm talking about huge p, order of 2^256. That's what I meant by saying sub-exponential algorithm. – valdo Jun 05 '18 at 04:50

1 Answers1

1

If I understand the problem correctly, you are trying to map a quadratic residue $\pmod p$, to a quadratic non-residue $\pmod p$. The mapping $a$ to $-a$ works if $p = 3 \pmod 4$.

J. Linne
  • 3,022