An Indexing for Quadratic Residues Modulo $N$ and a Non-uniform Efficient Decoding Algorithm

An \emph{indexing} of a finite set $S$ is a bijection $D : {1,…,|S|} \rightarrow S$\mathrm{.}Wepresentanindexingforthesetofquadraticresiduesmodulo$N$thatisdecodableinpolynomialtimeonthesizeof$N$, given the factorization of $N$. One consequence of this result is a procedure for sampling quadratic residues modulo $N$, when the factorization of $N$ is known, that runs in strict polynomial time and requires the theoretical minimum amount of random bits (i.e., $\log (\varphi (N)\mathrm{/}{2}^r)$ bits, where $\varphi (N)$ is Euler’s totient function and $r$ is the number of distinct prime factors of $N$). A previously known procedure for this same problem runs in expected (not strict) polynomial time and requires more random bits.