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?
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$.